CICA 1993 April

home *** CD-ROM | disk | FTP | other *** search

/ CICA 1993 April / CICA MS Windows - April 1993.iso / unzipped / programr / bcpp / classlib / classlib.doc next >

Wrap

Text File | 1992-02-14 | 263KB | 6,845 lines

Online document ___________________________________________________________________________ The container class libraries For more Turbo C++ version 3.0 includes two complete container information about class libraries: an enhanced version of the Object- templates, see based library supplied with version 1.0, plus a brand- Chapter 13, "C++ new implementation based on templates. This chapter specifics." describes both libraries. We assume that you are familiar with the syntax and semantics of C++ and with the basic concepts of object-oriented programming (OOP). To understand the template-based version (called BIDS, for Borland International Data Structures), you should be acquainted with C++'s new template mechanism. The chapter is divided into seven parts: o A review of the difference between versions 1.0 and 3.0 of the class libraries o An overview of the Object- and template-based libraries o A survey of the Object container classes, introducing the basic concepts and terminology o An overview of the BIDS library o The CLASSLIB directory and how to use it o Debugging tools o An alphabetic reference guide to the Object container library, listing each class and its members =========================================================================== What's new since version 1.0? =========================================================================== The version 1.0 container library is an Object-based implementation. Both container objects and the elements stored in them are all ultimately derived from the - 1 - class Object. Further, the data structures used to implement each container class were fixed and (usually) hidden from the programmer. This provides a simple, effective model for most container applications. Version 3.0 therefore offers an enhanced, code- compatible version of the previous Object-based container library. We call this the Object container class library. In addition, a more flexible (but more complex), template-based container library, called BIDS (Borland International Data Structures), is supplied with version 3.0. Through the power of templates, BIDS lets you vary the underpinning data structure for a container and lets you store arbitrary objects in a container. With the appropriate template parameters, BIDS can actually emulate the Object container library. Before we review the differences between the Object and BIDS models, we'll list the changes to the Object container library since version 1.0: o New Btree and PriorityQueue classes. o New TShouldDelete class gives the programmer control over container/element ownership. You can control the fate of objects when they are detached from a container and when the container is flushed (using the new flush method) or destroyed. o New memory management classes, MemBlocks and MemStack, for efficient memory block and memory stack (mark-and-release) allocations. o New PRECONDITION and CHECK macros provide sophisti- cated assert mechanisms to speed application develop- ment and debugging. o New Timer class gives you a stopwatch for timing program execution. When you choose Existing Turbo C++ version 1.01 container class code Container Class will still run with the version 3.0 libraries. The new Library in the Object container class libraries, in directory IDE's Options| \CLASSLIB, are distinguished by the prefix TC: Linker|Libraries TCLASSx.LIB and TCLASDBx.LIB where x specifies the dialog box, the memory model, and DB indicates the special debug Object-based version. To reduce verbiage, we will often refer to libraries will be this container implementation as the Object or TC automatically version. linked in. - 2 - To use the The corresponding libraries for the new template-based template-based container classes are distinguished by the prefix BIDS: libraries, you BIDSx.LIB and BIDSDBx.LIB. Let's review the reasons for must explicitly having two sets of container libraries. The use of all add the these libraries is covered on page 31. appropriate BIDS[DB]x.LIB library to your project or makefile. =========================================================================== Why two sets of libraries? =========================================================================== The Object container classes have been retained and enhanced to provide code compatibility with the version 1.0 library. They provide a gentler learning curve than the template-based BIDS library. The Object container code offers faster compilation but slightly slower execution than the template version. The project files for the example and demo programs are set up to use the Object version of the container libraries. BIDS exploits the new exciting templates feature of C++ 2.1. It offers you considerable flexibility in choosing the best underlying data structure for a given container application. With the Object version, each container is implemented with a fixed data structure, chosen to meet the space/speed requirements of most container applications. For example, a Bag object is implemented with a hash table, and a Deque object with a double list. With BIDS you can fine-tune your application by varying the container implementation with the minimum recoding--often a single typedef will suffice. You can switch easily from StackAsList to StackAsVector and test the results. In fact, you'll see that by setting appropriate values for <T>, a generic class parameter, you can implement the Object model exactly. With BIDS, you can even choose between polymorphic and non-polymorphic implementations of the Object container model. Such choices between execution speed (non-polymorphic) and future flexibility (polymorphic) can be tested without major recoding. - 3 - Existing code Both the Object and BIDS versions provide the same based on the functional interface. For example, the push and pop Object container member functions work the same for all Stack objects. classes will This makes the new template-based libraries highly compile and run compatible with existing code written for the Object perfectly using library. the new BIDS classes, just by The objects stored in Object library containers must be linking in the derived from the class Object. To store ints, say, you appropriate would have to derive an Integer class from Object library. (you'll see how later). With BIDS you have complete freedom and direct control over the types of objects stored in a container. The stored data type is simply a value passed as a template parameter. For instance, BI_ListImp<int> gives you a list of ints. Regardless of which container class model you elect to use, you should be familiar with container terminology, the Object class hierarchy, and the functionality provided for each container type. Although the classes in the BIDS library have different naming conventions and special template parameters, the prototypes and functionality of each class member are the same as those in the Object library. =========================================================================== Container basics =========================================================================== If you are fully We start by describing the Object container class versed in the hierarchy as enhanced for Turbo C++ version 3.0. This Turbo C++ 1.0 hierarchy offers a high degree of modularity through version of the inheritance and polymorphism. You can use these classes container library, as they are, or you can extend and expand them to pro- you should first duce an object-oriented software package specific to check out the your needs. Object library enhancements At the top of the class hierarchy is the Object class before moving to (see Figure 1), an abstract class that cannot be the templates instantiated (no objects of its type can be declared). section on page An abstract class serves as an umbrella for related 14. classes. As such, it has few if any data members, and some or all of its member functions are pure virtual functions. Pure virtual functions serve as placeholders for functions of the same name and signature intended - 4 - to be defined eventually in derived classes. In fact, any class with at least one pure virtual function is, by definition, an abstract class. Figure 1: Class hierarchies in CLASSLIB Object─┬─Error ├─Sortable────┬─String │ ├─BaseDate─────Date │ └─BaseTime─────Time ├─Association └─Container───┬─Collection─┬─AbstractArray─┬─Array │ │ └─SortedArray │ ├─HashTable │ ├─Bag──Set──Dictionary │ ├─List │ ├─Btree │ └─DoubleList ├─Stack ├─Deque──Queue └─PriorityQueue ContainerIterator────┬─HashTableIterator ├─ListIterator ├─DoubleListIterator ├─BtreeIterator └─ArrayIterator Memblocks MemStack Note that TShouldDelete provides a second base (multiple inheritance) for both Container and Association. A class derived from an abstract class can provide a body defining the inherited pure virtual function. If it doesn't, the derived class remains abstract, providing a base for further derivations. When you reach a derived class with no pure virtual functions, the class is called a non-abstract or instance class. As the name implies, instance classes can be instantiated to provide usable objects. An abstract class can be the base for both abstract and instance classes. For example, you'll see that Container, an abstract class derived from the abstract class Object, is the base for both Collection (abstract) and Stack (instance). - 5 - To enhance your As you read this chapter, bear in mind that a derived understanding of class inherits and can access all non-private data the classes, you members and member functions from all its ancestral can review their base classes. For example, the Array class does not declarations in need to explicitly define a function to print an array, the source code because its immediate parent class AbstractArray does files in the so. The Container class, an ancestor further up the CLASSLIB class tree, defines a different print function that can directory. also be used with an array, because an array is a container. To determine all the member functions available to an object, you will have to ascend the class hierarchy tree. Because the public interface is intended to be sufficient for applications, object- oriented programming makes a knowledge of private data members unnecessary; therefore, private members (with a few exceptions) are not documented in this chapter. ------------------ The Object-based hierarchy contains classes derived Object-based and from the class Object (together with some other utility other classes classes). Object provides a minimal set of members ------------------ representing what every derived object must do; these are described in the reference section under Object (page 84). Both the containers-as-objects and the objects they store are objects derived (ultimately) from Object. Later you'll see that the template-based containers can contain objects of any data type, not just those derived from Object. Class categories ======================================================= The classes in or near the Object hierarchy can be divided into three groups: o The non-container classes include Object itself, and those classes derived from Object, such as String and Date, which cannot store other objects. o The container classes (also derived from Object), such as Array and List, which can store objects of other, usually non-container, class types. o The helper and utility classes not derived from Object, such as TShouldDelete, ListIterator and MemStack. Let's look at each category in more detail, although as with most OOP topics, they are closely related. - 6 - Non-container ======================================================= classes The basic non-container classes provided are Object and its three children: Error (instance), Sortable (abstract), and Association (instance). Recall that the main purpose of these classes is to provide objects that can be stored as data elements in containers. To this end, all Object-derived classes provide a hashing function allowing any of their objects to be stored in a hash table. ------------------ Error is not a normal class; it exists solely to define Error class a unique, special object called theErrorObject. A ------------------ pointer to theErrorObject carries the mnemonic Error see page 74 NOOBJECT. NOOBJECT is rather like a null pointer, but in the reference serves the vital function of occupying empty slots in a section. container. For example, when an Array object is created (not to be confused with a traditional C array), each of its elements will initially contain NOOBJECT. ------------------ Sortable is an abstract class from which sortable Sortable class classes must be derived. Some containers, known as ------------------ ordered collections, need to maintain their elements in a particular sequence. Collections such as SortedArray and PriorityQueue, for example, must have consistent methods for comparing the "magnitude" of objects. Sortable adds the pure virtual function isLessThan to its base, Object. Classes derived from Sortable need to define IsLessThan and IsEqual (inherited from Object) for their particular objects. Using these members, the relational operators <, ==, >, >=, and so on, can be overloaded for sortable objects. Typical sortable classes are String, Date, and Time, the objects of which are ordered in the natural way. Of course, string ordering may depend on your locale, but you can always override the comparison functions (another plus for C++). For more details Distinguish between the container object and the on Sortable see objects it contains: Sortable is the base for non- page 93 in the container objects; it is not a base for ordered reference section. collections. Every class derived from Object inherits the isSortable member function so that objects can be queried as to their "sortability." - 7 - ------------------ Association is a non-container, instance class Association class providing special objects to be stored (typically) in ------------------ Dictionary collections. An Association object, known as Association see an association, is a pair of objects known as the key page 44 in the and the value. The key (which is unique in the reference section. dictionary) can be used to retrieve the value. Every class derived from Object inherits the isAssociation member function so that objects can report whether they are associations or not. Container classes ======================================================= In the Object-based library, all the container storage and access methods assume that the stored elements are derived from Object. They are actually stored as references or pointers to Object offering the advantages and disadvantages of polymorphism. Most of the container access member functions are virtual, so a container does not need to "know" how its contained elements were derived. A container can, in theory, contain mixed objects of different class types, so proper care is needed to maintain type-safe linkage. Every class has member functions called IsA and nameOf, which allow objects to announce their class ID and name. As you've seen, there are also isSortable and isAssociation member functions for testing object types. All the container classes are derived from the abstract Container class, a child of Object. Container encapsulates just a few simple properties upon which more specialized containers can be built. The basic container provides the following functionality: o Displays its elements o Calculates its hash value o Pure virtual slot for counting the number of items with getItemsInContainer o Pure virtual slot for flushing (emptying) the container with flush o Performs iterations over its elements o Reports and changes the ownership of its elements (inherited from TShouldDelete) So far, our containers have no store, access, or detach methods. (We can flush the container but we cannot detach individual elements.) Nor is there a hasMember - 8 - member function, that is, a general way of determining whether a given object is an element of the container. This is a deliberate design decision. As we move up the hierarchy, you'll see that what distinguishes the various derived container classes are the storage and access rules that actually define each container's underlying data structure. Thus push and pop member functions are added for Stack, indexing operators are added for Array, and so on. There is not enough in common to warrant having generic add and retrieve methods at the Container level. There is no one perfect way of extracting common properties from groups of containers, and therefore no perfect container class hierarchy. The Object-based container hierarchy is just one possible design based on reasonable compromises. The BIDS version, as you'll see, offers a different perspective. The first three Container functions listed previously are fairly self-explanatory. We'll discuss the important subjects of ownership and iteration in the next two sections. Containers and ======================================================= ownership Before you use the Container family, you must understand the concept of ownership. As in real life, a C++ container starts out empty and must be filled with objects before the objects can be said to be in the container. Unlike the real world, however, when objects are placed in the container, they are, by default, owned by the container. The basic idea is that when a container owns its objects, the objects are destroyed when the container is destroyed. Recall that containers are themselves objects subject to the usual C++ scoping rules, so local containers come and go as they move in and out of scope. Care is needed, therefore, to prevent unwanted destruction of a container's contents, so provision is made for changing ownership. A container can, throughout its lifetime, relinquish and regain ownership of its objects as often as it likes by calling the ownsElements member function (inherited from TShouldDelete). The fate of its objects when the container disappears is determined by the ownership status ruling at the time of death. Consider the following: - 9 - void test() { Array a1( 10 ); // construct an array Array a2( 10 ); // and another a1.ownsElements( 1 ); // array a1 owns its objects (the default) a2.ownsElements( 0 ); // array a2 relinquishes ownership // load and manipulate the arrays here } When test exits, a1 will destroy its objects, but the objects in a2 will survive (subject, of course, to their own scope). The a1.ownsElements( 1 ) call is not really needed since, by default, containers own their contents. Ownership also plays a role when an object is removed from a container. The pure virtual function Container::flush is declared as virtual void flush( DeleteType dt = DefDelete ) = 0; flush empties the container but whether the flushed objects are destroyed or not is controlled by the dt argument. DeleteType is an enum defined in TShouldDelete. A value of NoDelete means preserve the flushed objects regardless of ownership; Delete means destroy the objects regardless of ownership; DefDelete, the default value, means destroy the objects only if owned by the container. Similarly Collection (derived from Container) has a detach member function, declared as virtual void detach( Object& obj, DeleteType dt = NoDelete ) = 0; which looks for obj in the collection and removes it if found. Again, the fate of the detached object is determined by the value dt. Here, the default is not to destroy the detached object. Collection::destroy is a variant that calls detach with DefDelete. A related problem occurs if you destroy an object that resides in a container without "notifying" the - 10 - container. The safest approach is to use the container's methods to detach and destroy its contents. Important! If you declare an automatic object (an object that's local to your routine) and place that object in a global container, your local object will be destroyed when the routine leaves the scope in which it was declared. To prevent this, you must only add heap objects (objects that aren't local to the current scope) to global containers. Similarly, when you remove an object from a global container, you are responsible for destroying it and freeing the space in which it resides. Container ======================================================= iterators You saw earlier that Container, the base for all containers in the Object-based library, supports iteration. Iteration means traversing or scanning a container, accessing each stored object in turn to perform some test or action. The separate ContainerIterator-based hierarchy provides this functionality. Iterator classes are derived from this base to provide iterators for particular groups of containers, so you'll find HashTableIterator, ListIterator, BtreeIterator, and so on. Under There are two flavors of iterators: internal and ContainerIterator external. Each container inherits the three member on page 64 in the functions: firstThat, lastThat, and forEach, via the reference section, Object and Container classes. As the names indicate, you see how the these let you scan through a container either testing pre- and post- each element for a condition or performing an action on increment each of the container's elements. When you invoke one operators ++ are of these three member functions, the appropriate overloaded to iterator object is created for you internally to simplify your support the iteration. Most iterations can be performed iterator programs. in this way since the three iterating functions are very flexible. They take a pointer-to-function argument together with an arbitrary parameter list, so you can do almost anything. For even more flexibility, there are external iterators that you can build via the initIterator member function. With these, you have to set up your own loops and test for the end-of- container. - 11 - Returning to the container class hierarchy, we look at three classes derived directly from Container: Stack, Deque, and PriorityQueue. Sequence classes ======================================================= The instance classes Stack, Deque (and its offspring Queue), and PriorityQueue are containers collectively known as sequence classes. A sequence class is characterized by the following properties: 1. Objects can be inserted and removed. 2. The order of insertions and deletions is significant. 3. Insertions and extractions can occur only at specific points, as defined by the individual class. In other words, access is nonrandom and restricted. Sequences (like all containers) know how many elements they have (using getItemsInContainer) and if they are empty or not (using isEmpty). However, they cannot usually determine if a given object is a member or not (there is still no general hasMember or findMember member function). Stacks, queues, priority queues, and deques vary in their access methods as explained in more detail in the reference section. Sequence is not itself a class because sequences do not share enough in common to warrant a separate base class. However, you might find it helpful to consider the classes together when reviewing the container hierarchy. Collections ======================================================= The next level of specialization is the abstract class Collection, derived from Container, and poised to provide a slew of widely used data structures. The key difference between collections and containers is that we now have general hasMember and findMember member functions. From Collection we derive the unordered collections Bag, HashTable, List, DoubleList, and AbstractArray, - 12 - and the ordered collection Btree. In turn, AbstractArray spawns the unordered Array and the ordered SortedArray. Bag serves as the base for Set which in turn is the base for Dictionary. These collections all refine the storage and retrieval methods in their own fashions. ------------------ With unordered collections, any objects derived from Unordered Object can be stored, retrieved, and detached. The collections objects do not have to be sortable because the access ------------------ methods do not depend on the relative "magnitude" of the elements. Classes that fall into this category are o HashTable o Bag, Set, and Dictionary o List and DoubleList o Array ------------------ An ordered collection depends on relative "magnitude" Ordered when adding or retrieving its elements. Hence these collections elements must be objects for which the isLessThan ------------------ member function is defined. In other words, the elements in an ordered collection must be derived from the class Sortable. The following are ordered collections: o Btree o SortedArray =========================================================================== The BIDS template library =========================================================================== The BIDS container class library can be used as a springboard for creating useful classes for your individual needs. Unlike the Object container library, BIDS lets you fine-tune your applications by varying the underlying data structures for different containers with minimum reprogramming. This extends the power of encapsulation: the implementor can change the internals of a class with little recoding and the user can easily replace a class with one that provides a more appropriate algorithm. The BIDS class library achieves this flexibility by using the C++ template mechanism. - 13 - For a basic With BIDS, the container is considered as an ADT description of C++ (abstract data type), and its underlying data structure templates see is independently treated as an FDS (fundamental data Chapter 13. structure). BIDS also allows separate selections of the type of objects to be stored, and whether to store the objects themselves or pointers to objects. Templates, ======================================================= classes, and containers Computer science has devoted much attention to devising suitable data structures for different applications. Recall Wirth's equation, Programs = Algorithms + Data Structures, which stresses the equal importance of data structures and their access methods. As used in current OOP terminology, a container is simply an object that implements a particular data structure, offering member functions for adding and accessing its data elements (usually other objects) while hiding from the user as much of the inner detail as possible. There are no simple rules to determine the best data structure for a given program. Often, the choice is a compromise between competing space (RAM) and time (accessibility) considerations, and even here the balance can shift suddenly if the number of elements or the frequency of access grows or falls beyond a certain number. Container ======================================================= implementation Often, you can implement the desired container properties in many ways using different underlying data structures. For example, a stack, characterized by its Last-In-First-Out (LIFO) access, can be implemented as a vector, a linked list, or perhaps some other structure. The vector-based stack is appropriate when the maximum number of elements to be stored on the stack is known in advance. A vector allocates space for all its elements when it is created. The stack as a list is needed when there is no reasonable upper bound to the size of the stack. The list is a slower imple- mentation than the vector, but it doesn't use any more memory than it needs for the current state of the stack. - 14 - The way objects are stored in the container also affects size and performance: they can be stored directly by copying the object into the data structure, or stored indirectly via pointers. The type of data to be stored is a key factor. A stack of ints, for example, would probably be stored directly, where large structs would call for indirect storage to reduce copying time. For "in-between" cases, however, choosing strategies is not always so easy. Performance tuning requires the comparison of different container implementations, yet traditionally this entails drastic recoding. The template ======================================================= solution The template approach lets you develop a stack-based application, say, using vectors as the underlying structure. You can change this to a list implementation without major recoding (a single typedef change, in fact). The BIDS library also lets you experiment with object-storage strategies late in the development cycle. Each container-data structure combination is implemented with both direct and indirect object storage, and the template approach allows a switch of strategy with minimal rewriting. The data type of the stored elements is also easy to change using template parameters, and you are free to use any data type you want. As you'll see, BIDS offers container/data structure combinations that match those of the Object-based version. For example, the Object library implements Stack using lists, so Stack can be simulated exactly with the template class BI_TCStackAsList. Let's look at the template approach in more detail. - 15 - ------------------ We discussed earlier the stack and its possible ADTs and FDSs implementations as a linked list or as a vector. The ------------------ potential for confusion is that stacks, lists, and vectors are all commonly referred to as data structures. However, there is a difference. We can define a stack abstractly in terms of its LIFO accessibility, but it's difficult to envision a list without thinking of specifics such as nodes and pointers. Likewise, we picture a vector as a concrete sequence of adjacent memory locations. So we call the stack an ADT (abstract data type) and we call the list and vector FDSs (fundamental data structures). The BIDS container library offers each of the standard ADTs implemented with a choice of appropriate FDSs. Table 1 indicates the combinations provided: ADTs as fundamental data ------------------------------------------------------- structures ADT Sorted FDS Stack Queue Deque Bag Set Array Array ------------------------------------------------------- Vector x x x x x x x List x DoubleList x x ------------------------------------------------------- The abstract data types involved are Stacks, Queues, Deques, Bags, Sets, and Arrays. Each ADT can be implemented several different ways using the fundamental data structures Vector, List, and DoubleList as indicated by a bullet ( x ) in the table. Thus, all ADTs are implemented as vectors. In addition, Stacks are implemented as a list; Queues and Deques implemented as doubly-linked lists. (Not shown in the table are the sorted and counted FDSs from which various ADTs can be developed.) There is nothing sacred about these combinations; you can use the template classes to develop your own ADT/FDS implementations. - 16 - ------------------ ADTs are implemented in both direct and indirect Class templates versions. The direct versions store the objects ------------------ themselves, while the indirect versions store pointers to objects. You can store whatever objects you want as elements in these FDSs using the power of templates. Here are the ADT and FDS templates we provide: --------------------------------------------------------------------------- Table 2: FDS class templates Class template Description --------------------------------------------------------------------------- BI_VectorImp<T> vector of Ts BI_VectorIteratorImp<T> iterator for a vector of Ts BI_CVectorImp<T> counted vector of Ts BI_SVectorImp<T> sorted vector of Ts BI_IVectorImp<T> vector of pointers to T BI_IVectorIteratorImp<T> iterator for a vector of pointers to T BI_ICVectorImp<T> counted vector of pointers to T BI_ISVectorImp<T> sorted vector of pointers to T BI_ListImp<T> list of Ts BI_SListImp<T> sorted list of Ts BI_IListImp<T> list of pointers to T BI_ISListImp<T> sorted list of pointers to T BI_DoubleListImp<T> double-linked list of Ts BI_SDoubleListImp<T> sorted double-linked list of Ts BI_IDoubleListImp<T> double-linked list of pointers to T BI_ISDoubleListImp<T> sorted double-linked list of pointers to T --------------------------------------------------------------------------- Each basic FDT has a direct and indirect iterator; to save space we have shown only the Vector iterators. The BI_ prefix stands for Borland International and the suffix Imp for implementation. The indirect versions have the prefix BI_I with the extra I for Indirect. The extra prefixes S and C mean Sorted and Counted respectively. The template parameter T in <T> represents the data type of the objects to be stored. You instantiate the template by supplying this data type. For example, BI_ListImp<double> gives you a list of doubles. See Table 3 on page 19 for a summary of these abbreviations. For direct object storage, the - 17 - type T must have meaningful copy semantics and a default constructor. Indirect containers, however, hold pointers to T, and pointers always have - 18 - good copy semantics. This means that indirect containers can contain objects of any type. Abbreviations in CLASSLIB names ----------------------------------------------------------------- Abbreviation Description ----------------------------------------------------------------- I Indirect C Counted S Sorted O Object-based, non-polymorphic TC Object-based, polymorphic (compatible with original Turbo C++ library) ----------------------------------------------------------------- For details see For the sorted FDSs (BI_SVectorImp, BI_ISVectorImp, and the discussion so on), T must have valid == and < operators to define under Sortable on the ordering of the elements. It should be clear that page 94. the IS variants refer to the objects being sorted, not that the pointers to the objects are sorted. Each implementation of an ADT with an FDS is named using the convention (ADT)As(FDS)<T>, as follows: ---------------------------------------------------------------------------- Table 4: ADT class templates Class name Description ---------------------------------------------------------------------------- BI_StackAsVector<T> Stack of Ts as a vector BI_QueueAsVector<T> Queue of Ts as a vector BI_DequeAsVector<T> Deque of Ts as a vector BI_BagAsVector<T> Bag of Ts as a vector BI_SetAsVector<T> Set of Ts as a vector BI_ArrayAsVector<T> Array of Ts as a vector BI_SArrayAsVector<T> Sorted array of Ts as a vector BI_IStackAsVector<T> Stack of pointers to T as a vector BI_IQueueAsVector<T> Queue of pointers to T as a vector ... and so on BI_StackAsList<T> Stack of Ts as a list BI_IStackAsList<T> Stack of pointers to T as a list - 19 - Table 4: ADT class templates (continued)___________________________________ BI_QueueAsDoubleList<T> Queue of Ts as a double list BI_DequeAsDoubleList<T> Deque of Ts as a double list BI_IQueueAsDoubleList<T> Queue of pointers to T as a double list BI_IDequeAsDoubleList<T> Deque of pointers to T as a double list ---------------------------------------------------------------------------- There are also Again, the <T> argument, either a class or predefined BI_Oxxx and data type, provides the data type for the contained BI_TCxxx variants elements. Each of the bulleted items ( x ) in Table 1 discussed soon. can be mapped to two templates (direct and indirect versions) with names following this convention. Container class ======================================================== compatibility Each template must be instantiated with a particular data type as the type of the element that it will hold. This allows the compiler to generate the correct code for dealing with any possible type of element without restricting the elements to just those derived from Object. Each ADT is also used to instantiate two classes that imitate the behavior of the Object class libraries. Here is a list of them: -------------------------------------------------------- Object-based FDS Class name Description classes -------------------------------------------------------- BI_OStackAsVector Stack of pointers to Object, as a vector BI_OQueueAsVector Queue of pointers to Object, as a vector BI_ODequeAsVector Deque of pointers to Object, as a vector BI_OBagAsVector Bag of pointers to Object, as a vector BI_OSetAsVector Set of pointers to Object, as a vector BI_OArrayAsVector Array of pointers to Object, as a vector BI_OSArrayAsVector Sorted array of pointers to Object, as a vector - 20 - Table 5: Object-based FDS classes (continued)__________ BI_TCStackAsVector Polymorphic stack of pointers to Object, as a vector BI_TCQueueAsVector Polymorphic queue of pointers to Object, as a vector BI_TCDequeAsVector Polymorphic deque of pointers to Object, as a vector BI_TCBagAsVector Polymorphic bag of pointers to Object, as a vector BI_TCSetAsVector Polymorphic set of pointers to Object, as a vector BI_TCArrayAsVector Polymorphic array of pointers to Object, as a vector BI_TCSArrayAsVector Polymorphic sorted array of pointers to Object, as a vector BI_OStackAsList Stack of pointers to Object, as a list BI_TCStackAsList Polymorphic stack of pointers to Object, as a list BI_OQueueAsDoubleList Queue of pointers to Object, as a double list BI_ODequeAsDoubleList Deque of pointers to Object, as a double list BI_TCQueueAsDoubleList Polymorphic queue of pointers to Object, as a double list BI_TCDequeAsDoubleList Polymorphic deque of pointers to Object, as a double list -------------------------------------------------------- Note that these versions have no explicit <T> parameters; they use the fixed data types shown The TCxxx versions (pointers to Object). The BI_Oxxx (O for Object library) offer the same versions of these classes have no virtual functions. behavior and This makes it easier for the compiler to generate inline interfaces as the function expansions, which in turn makes the BI_Oxxx Object library. versions of the containers somewhat faster than the corresponding polymorphic BI_TCxxx (TC for Turbo C++) versions. The obverse of the coin is that the BI_Oxxx versions do not share the polymorphic behavior of the Object container library. - 21 - In the Object container library, Stack implements a stack as a polymorphic list of pointers to Object. The BIDS class BI_TCStackAsList therefore mirrors the Object-based class Stack. Even with BI_TCStackAsVector, the public interface and semantics are the same as for the Object-based Stack. The user "sees" the ADT while the FDS is "hidden." For these reasons, we will not repeat the alphabetic list of Object-based classes and member functions for the BIDS library. Consider your many choices when writing container code with the BIDS model. You can gain speed over future flexibility by using the non-polymorphic classes, such as BI_OStackAsList or BI_OStackAsVector. Or you can retain the polymorphism of the Object-based hierarchy by using the BI_TCxxx classes. Header files ======================================================== Each group of FDSs is defined in its own header file, which contains templates for both the direct and the indirect versions. The names of the headers are as follows: vectimp.h listimp.h dlistimp.h In vectimp.h, for example, you'll find declarations for all the vector, counted vector, and sorted vector templates, together those for a direct and indirect vector iterator. Note also the stdtempl.h file that defines the useful template functions min, max, and range. If you are new to templates, this file offers a useful, gentle introduction to the subject. Each ADT family is defined in its own header file, named as follows: stacks.h queues.h deques.h bags.h sets.h arrays.h - 22 - Note the plural The file stacks.h, for example, defines the following form that templates: distinguishes the BIDS include files BI_StackAsVector<T> from the Object- BI_IStackAsVector<T> based include file BI_OStackAsVector BI_TCStackAsVector BI_StackAsList<T> BI_IStackAsList<T> BI_OStackAsList BI_TCStackAsList Tuning an ======================================================== application Consider the following example: typedef BI_StackAsVector<int> intStack; int main() { intStack is; for( int i = 0; i < 10; i++ ) is.push( i ); for( i = 0; i < 10; i++ ) cout << is.pop() << endl; return(0); } Here we are implementing a stack of ints using a vector as the underlying data structure. If you later determine that a list would be a more suitable implementation for the stack, you can simply replace the typedef with the following: typedef BI_StackAsList<int> intStack; After recompilation, the stack implementation is changed from vector to list. Similarly, you can try a stack of pointers to int, with: typedef BI_IStackAsList<int> intStack; - 23 - FDS implementation ======================================================== Each FDS is implemented as two templates, one that provides the direct version, and one that provides the indirect version. The indirect version makes use of an InternalIxxxImp class. The following simplified extract from listimp.h will give you an idea how the different list FDSs are implemented. Note that BI_ListElement<T> is an internal template class used to implement the node (data of type T and pointer to next node) of a list. The direct list of objects of type T is implemented by the template class BI_ListImp<T>, which also provides the base for BI_SListImp<T> (sorted lists). The example shows how the add member function is implemented in the direct, indirect, sorted and unsorted lists. template <class T> class BI_ListElement { public: BI_ListElement( T t, BI_ListElement<T> *p ) : data(t) { next = p->next; p->next = this; } // constructor ... BI_ListElement<T> *next; // pointer to next node T data; // object at node ... }; template <class T> class BI_ListImp // linked list (unsorted) of type T objects; assumes T has meaningful // copy semantics and a default constructor { public: ... void add( T t ) { new BI_ListElement<T>( t, &head ); } // adds objects at head of list (shown inline here to save space) T peekHead() const { return head.next->data; } ... }; template <class T> class BI_SListImp : public BI_ListImp<T> // sorted list; assumes T has meaningful copy - 24 - // semantics and a default constructor { public: ... void add( T t ) { new BI_ListElement<T>( t, findPred(t) ); } // adds object in sorted position ... }; template <class T, class List> class BI_InternalIListImp : public List { ... void add( T *t ) { List::add ( t ); } }; // The work is done in this intermediate class // used as base for BI_IListImp; list is // unsorted so we use List::add template <class T> class BI_IListImp : public BI_InternalIListImp<T, BI_ListImp< void * > > { ... }; /* unsorted list of pointers to objects of type T; since pointers always have meaningful copy semantics, this class can handle any object type; add comes straight from BI_InternalIListImp */ template <class T> class BI_ISListImp : public BI_InternalIListImp<T>, BSListImp< void * >> { ... }; /* sorted list of pointers to objects of type T; since pointers always have meaningful copy semantics, this class can handle any object type */ In addition to the template classes shown here, listimp.h also declares BI_ListIteratorImp<T> and BI_IListIteratorImp<T>, the iterators for direct and indirect lists. In the next section on ADTs, you'll see how the different stack implementations in stacks.h pull in the vector and list FDSs declared in vectimp.h and listimp.h. - 25 - The double list templates, in dlistimp.h, follows the same pattern. The sorted versions of list and double list provide exactly the same interface as the non- sorted ones, except that the add member function adds new elements in sorted order. This speeds up subsequent access and also makes it easier to implement priority queues. vectimp.h also follows a similar pattern to listimp.h, implementing BI_VectorImp<T> (direct) and BI_IVectorImp<T> (indirect). These are low-level vectors with no notion of add or detach. To support more sophisticated ADTs, the counted vector, BI_CVectorImp<T>, derived from BI_VectorImp<T>, is provided. This maintains a pointer to the last valid entry in the underlying Vector. It has an add member function that inserts its argument at the top (the next available slot), and a detach member function that removes its argument and compresses the array. BI_CVectorImp<T> provides the base for the sorted vector template BI_SVectorImp<T>. With a sorted vector, you can run through the indices from 0 to the last valid entry, and the objects will emerge in sort order. Here's a simplified extract from vectimp.h: // extract from vectimp.h template <class T> class BI_VectorImp { ... }; // direct uncounted, unsorted vector template <class T> class BI_CVectorImp : public BI_VectorImp<T> // direct counted, unsorted vector { public: ... void add( T t ); // add at top of array; inc count; resize array if necessary void detach( T t, int del = 0 ); void detach( unsigned loc, int del = 0 ); // detach given object or object at loc ... }; template <class T> class BI_SVectorImp : public BI_CVectorImp<T> // direct counted, sorted vector - 26 - { public: void add( T t ); // add at position that maintains sort }; template <class T, class Vect> class BI_InternalIVectorImp : public Vect {...}; // interdiate base for BI_IVectorImp: no add template <class T> class BI_IVectorImp : public BI_InternalIVectorImp<T, BI_VectorImp<void *> > {...}; // indirect uncounted, unsorted vector: no add template <class T, class Vect> class BI_InternalICVectorImp : public BI_InternalIVectorImp<T, Vect> // intermediate base for BI_ICVector { public: void add( T *t) { Vect::add(t); } ... }; template <class T> class BI_ICVectorImp : public BI_InternalICVectorImp<T, BI_CVectorImp<void *> > { ... }; // indirect counted vector; can contain any object type template <class T> class BI_ISVectorImp : public BI_InternalICVectorImp<T, BI_SVectorImp<void *> > { ... }; // indirect sorted vector ADT implementation ======================================================== Each ADT is implemented as several templates. For example, the following provides an implementation of a stack of objects of type T using vectors as the FDS: // simplified extract from stacks.h - 27 - template <class Vect, class T> class BI_StackAsVectorImp { public: ... void push( T t ) { data[current++] = t; } ... protected: Vect data; unsigned current; }; The first parameter, class Vect, is either a direct vector or an indirect vector, depending on whether the stack being created is direct or indirect, so Vect will be either BI_VectorImp<T0> or BI_IVectorImp<T0>. The type T represents the type of objects to be stored in the stack. For a direct Vect, T should be the same as T0; for an indirect Vect, T must be of type pointer to T0. A direct stack implemented as a vector looks like this: template <class T> class BI_StackAsVector : public BI_StackAsVectorImp< BI_VectorImp<T>, T > { public: friend class BI_StackAsVectorIterator<T>; ... }; template <class T> class BI_StackAsVectorIterator : public BI_VectorIteratorImp<T> {...}; That is, a BI_StackAsVector is implemented by using a BI_StackAsVectorImp, whose "implementation" is of type BI_VectorImp<T>, and whose elements are of type T. BI_StackAsVector has its own iterator, derived from underpinning FDS iterator with the contained-object type T as parameter. An indirect stack implemented as a vector looks like this: template <class T> class BI_IStackAsVector : public BI_StackAsVectorImp< BI_IVectorImp<T>, T* >, public virtual TShouldDelete {...}; - 28 - That is, an BI_IStackAsVector is implemented by using a BI_StackAsVectorImp, whose "implementation" is of type BI_IVectorImp<T>, and whose elements are of type pointer to T. The TShouldDelete base provides the ownership control discussed in the Object-based class reference section. TShouldDelete also serves as a second base for the following classes. Figure 2: TShouldDelete hierarchy TShouldDelete*──────┬──Association* ├──Container ├──BI_IArrayAsVector+ ├──BI_IBagAsVector+ ├──BI_IDequeAsDoubleList+ ├──BI_IDequeAsVector+ *Instance classes ├──BI_ISArrayAsVector+ ├──BI_ISObjectArray+ ├──BI_IStackAsList+ +Template classes └──BI_IStackAsVector+ The BI_OStackAsVector and BI_TCStackAsVector versions (stacks of pointers to Objects, emulating the Object container library) now follow easily: class BI_OStackAsVector // non-polymorphic stack with vector of pointers to Objects { public: ... void push( Object *t ) { ostack.push(t); } // ostack is type BI_IStackAsVector<Object> // so we are pushing pointers to Object ... private: BI_IStackAsVector<Object> ostack; }; class BI_TCStackAsVector : public Container // polymorphic stack with vector of pointers to Objects // inherits from the Object-based Container class // Provides identical interface and functionality as Object-based Stack // class but underlying data structure is Vector not List - 29 - { public: ... void push( Object& o ) { stk.push( &o ); } // stk is type BI_OStackAsVector // so we are pushing Objects ... private: BI_OStackAsVector stk; }; We end the section with some short examples using the BIDS classes. Source #include <iostream.h> #include <strstream.h> Uses the template #include <arrays.h> facility to pick a #include <strng.h> specific FDS for the array ADT. int main() { typedef BI_SArrayAsVector<String> lArray; In the "sorted lArray a(2); array" FDS, the for (int i = a.arraySize(); i; i--) index of a { particular array ostrstream os; element depends on os << "string " << i << ends; its value, not on a.add( *(new String(os.str()))); the order in which } it was entered. cout << "array elements;\n"; for (i = 0; i < a.arraySize(); ++i) { If the ADT used cout<< a[i] << endl; BI_ArrayAsVector } <String>, the return(0); elements would } appear in the order they were added to the array. Output string 1 string 2 string 3 Source - 30 - Doubly-linked list #include <iostream.h> with indirect #include <strstream.h> storage as FDS. #include <deques.h> #include <strng.h> Pointers to String typedef BI_IDequeAsDoubleList<String> lDeque; objects in the deque container int main() must be { dereferenced when lDeque d; extracting from for (int i = 1; i < 5; i++) the deque. { ostrstream os; os << "string " << i << ends; // use alternating left, right insertions if(i&1) d.putLeft(new String(os.str())); else d.putRight(new String(os.str())); } cout << "Deque Contents:" << endl; while (!d.isEmpty()) { cout << *d.getLeft() << endl; } return(0); } Output Deque Contents: string 3 string 1 string 2 string 4 =========================================================================== The class library directory =========================================================================== The files in the class library are set up in the following directory structure: - 31 - ╔═══════════╗ ║ CLASSLIB\ ║ ╚═════╤═════╝ ┌──────────────┬──────────────┼───────────┬────────────┐ ╔════╧═════╗ ╔════╧════╗ ┌─────┴────┐ ╔══╧═══╗ ╔════╧══════╗ ║ INCLUDE\ ║ ║ SOURCE\ ║ │ OBJS │ ║ LIB\ ║ ║ EXAMPLES\ ║ ╚══════════╝ ╚═════════╝ └──────────┘ ╚══════╝ ╚═══════════╝ The CLASSLIB directory is under the TC directory. The contents of the directories in the class library are discussed in more detail in the following sections. The INCLUDE ======================================================= directory The INCLUDE directory contains the header files necessary to compile a program that uses the class library. You must put this directory on the include search path when you compile your program. Modify Options|Directories|Include Directories if you changed the default setup. For each BIDS ADT (abstract data type), such as Stack, there is a header file called stacks.h. The Object- based class Stack is declared in stack.h. If the identifier TEMPLATES is #defined, either in an .h file or via the command line _D option, then when stack.h is preprocessed, the Object-based declarations for Stack are bypassed and the template versions are included. In particular, if TEMPLATES is #defined, Stack is #defined as BI_TCStackAsList, so any code written for the Object-based Stack will be compiled with the BIDS version. The OBJS directory ======================================================= Subdirectories of the OBJS directory contain .PRJ file samples. The SOURCE ======================================================= directory The SOURCE directory contains the source files that implement many of the member functions of the classes in the library. These source files are provided as a guide for implementing new classes. - 32 - You also need these source files if you want to build a library. There are project files for small and large models, debug and non-debug versions, and template and non-template versions. ------------------ To create a new library using the small memory model, Creating a library proceed as follows: ------------------ 1. Open the CLASSLIBS\OBJS\S (for standard or BIDS) or CLASSLIBS\OBJS\DBS (for debug) directory. 2. Create a directory for the new library. 3. Copy the project file that's closest to the one you want to create to that directory (use TCLASSS.PRJ to create a standard classlib, TCLASDBS.PRJ to create a debug version, or BIDSS.PRJ to create a templatized version). 4. Rename the project file to TCLASSS.PRJ. 5. Run TC and select Project|Open TCLASSS.PRJ. 6. Set Options|Compiler|Code Generation to the small memory model. 7. Select Compile|Build all. 8. Copy the resultant .LIB file to the CLASSLIB\LIB directory. For a large memory model, in step 2 copy a xL.PRJ file and in step 3 rename it to TCLASSL.PRJ. Important! When you take a library that you have built and use it in one of the sample projects, you must update the project. See Chapter 7, "Managing multi-file projects" for more information. You must also be sure to compile your project with precisely the same switches and op- tions you used to build the library. If you don't have the same options, you will get warnings from the linker when the executable file is built. - 33 - The LIB directory ======================================================= The LIB directory contains the compiled source modules archived into a library. You must put this directory on the library search path when you link your program. For information about modifying the library search path, see Chapter 8, "The command-line compiler" (for command-line options). The Object-based container classes are in TCLASSx.LIB, where x is the memory-model designation (S for small, C for compact, M for medium, L for large, and H for huge). For each of these there are debugging versions TCLASDBx.LIB. The EXAMPLES ======================================================= directory The CLASSLIB\EXAMPLES directory contains the example programs and their project files. You can compile these programs to see how the parts of the class library are put together to form an application. Most of the examples use one or two of the classes in the hierarchy; other examples are more complex. Here is a list of the example programs and the classes that they use: 1. STRNGMAX: A very simple example using String. 2. REVERSE: An intermediate example using Stack and String. 3. LOOKUP: An intermediate example using Dictionary and Association. 4. QUEUETST: An intermediate example using Queue and introducing a non-hierarchical class, Time. 5. DIRECTRY: An advanced example illustrating derived user classes with SortedArray. - 34 - =========================================================================== Preconditions and checks =========================================================================== Version 3.0 offers some new debugging tools. The class libraries TCLASDBx.LIB and BIDSDBx.LIB (where x represents the memory model, S, C, L, M, or H) provide the debugging versions of TCLASSx.LIB and BIDSx.LIB. checks.h defines two macros, PRECONDITION( arg ) and CHECK( arg ). Each macro takes an arbitrary expression as an argument, just like assert. At runtime, if the expression evaluates to 0, an error message is displayed and execution terminates. If the expression evaluates to a nonzero value, execution continues in the normal fashion. Use PRECONDITION on entry to a function to check the validity of the arguments and to do any other checking to determine that the function has been invoked correctly. Use CHECK for internal checking during the course of execution of the function. Compilation of PRECONDITION and CHECK is controlled by the value of a manifest constant named __DEBUG. If __DEBUG has the value 0, PRECONDITION and CHECK are set to empty macros. In other words, setting __DEBUG to 0 removes all debugging. If __DEBUG has the value 1, PRECONDITION macros are expanded into the tests described above, but CHECK macros are empty. So, setting __DEBUG to 1 enables PRECONDITIONs and disables CHECKs. Setting __DEBUG to 2 or more, or not defining it at all, enables both forms of testing. Table 6 summarizes the available debugging modes: ----------------------------------------------------------------- Class debugging __DEBUG PRECONDITION CHECK modes ----------------------------------------------------------------- 0 Off Off 1 On Off >1 On On undefined On On - 35 - ----------------------------------------------------------------- When developing a class, set __DEBUG to 2 or leave it undefined. This gives you maximum checking when the code is still being worked on. When the class works properly, but the application that is going to use the class hasn't been completed, set __DEBUG to 1, so that incorrect calls from the application can be caught, without the additional overhead of the internal checking within the class. Once everything is working, set __DEBUG to 0 to remove all checking. Two versions of the .LIB file are provided that contain the class library code: one with PRECONDITIONs enabled, and one with no debugging. These are named TCLASDBX.LIB and TCLASSX.LIB, where X is replaced with the letter for the appropriate memory model: s, c, m, l, or h. The .LIB with DB in its name is the one with PRECONDITIONs enabled. =========================================================================== Container class reference =========================================================================== This section describes each class in the library as follows. We give the include file where it is defined, a diagram showing the parent of each class and immediate offspring, some introductory remarks, data members and member functions (with protoypes) listed alphabetically, what friendly relations exist, and, where appropriate, an example of the class's use. The members listed in the See also section belong to the class under discussion unless scope-qualified. Thus in the section on class X, you could find See also foo, Y::foo, and so on. The first foo refers to X::foo. Class derivations and class members are public unless otherwise noted as protected. We do not document destructors since they all perform the usual way. Most container classes have virtual destructors. - 36 - AbstractArray =========================================================================== AbstractArray abstarry.h =========================================================================== ┌────────────┐ ╔═════════════╗ ┌────────────┐ │ Collection ├──╢AbstractArray╟─┬─┤ Array │ └────────────┘ ╚═════════════╝ │ └────────────┘ │ ┌────────────┐ └─┤SortedArray │ └────────────┘ The abstract class AbstractArray offers random access to the elements of the collection via an indexing mechanism that maps a range of integers to the array elements. Indexes can be positive or negative integers with arbitrary lower and upper bounds (within the range of int). Arrays derived from AbstractArray can be dynamically resized as elements are added to them. The data member delta determines how many additional elements are assigned to the array when overflow occurs. AbstractArray exists because the derived classes SortedArray and Array have enough in common to warrant combining the common properties into an abstract base class. Since the derived classes differ only in the implementation of the member functions detach and the subscript operator, the remaining functions can be encapsulated in AbstractArray. Data members ======================================================= delta sizeType delta; protected delta represents the additional number of elements that will be assigned to the array if overflow occurs. If delta is zero, the array will not be resized following overflow. lastElementIndex int lastElementIndex; protected The index value of the last element added to the array. For an empty array this data member has the value (lowerbound - 1). lowerbound int lowerbound; protected - 37 - AbstractArray The lower bound of the array index, returned by the lowerBound member function. lowerbound is the minimum legal value of the absolute index. See also: lowerBound upperbound int upperbound; protected The current upper bound of the array index, returned by the upperBound member function. upperbound is the maximum legal value of the absolute index. See also: upperBound Member functions ======================================================= destroy void destroy( int atIndex ); Removes the object at the given index. Whether the object itself is destroyed or not depends on the array's ownership status. If the array currently owns the object, the object will be destroyed, otherwise the object survives. destroy is implemented with detach( atIndex, DefDelete ). arraySize sizeType arraySize() const; Returns the current number of cells allocated (upperbound - lowerbound + 1). constructor AbstractArray( int anUpper, int aLower = 0, sizeType aDelta = 0 ); Constructs and "zeroes" an array, given the upper and lower index bounds. The default lower bound is 0, the traditional origin for C arrays. The default delta is also zero, giving a fixed, nonresizable array. If delta is nonzero, run-time array overflow invokes the reallocate member function to provide more space (in increments of delta). A PRECONDITION is set to test if the lower bound is greater than or equal to the lower bound. detach virtual void detach( int atIndex, DeleteType dt = NoDelete ); - 38 - AbstractArray virtual void detach( Object& toDetach, DeleteType dt = NoDelete ); The first version removes the object at atIndex; the second version removes the object toDetach. The value of dt and the current ownership setting determine whether the object itself will be deleted. DeleteType is defined in the base class TShouldDelete as enum { NoDelete, DefDelete, Delete }. The default value of dt, NoDelete, means that the object will not be deleted regardless of ownership. With dt set to Delete, the object will be deleted regardless of ownership. If dt is set to DefDelete, the object will only be deleted if the array owns its elements. See also: TShouldDelete::ownsElements initIterator virtual ContainerIterator& initIterator() const; Creates an external iterator for this array. See also: ContainerIterator class isEqual int isEqual( const Object& testObject ) const; Returns 1 if the testObject array is equal to the calling array. Equal means that the two arrays have the same object ID, the arrays' dimensions are equal, and that their components are equal in each index position. Otherwise, isEqual returns 0. lowerBound int lowerBound() const; Returns the array's lowerbound. objectAt Object& objectAt( int atIndex ) const; protected Returns a reference to the element at the given index. See also: operator [] operator [] Object& operator []( int atIndex ) const; Returns a reference to the object at the given array index. printContentsOn void printContentsOn( ostream& outputStream ) const; - 39 - AbstractArray Prints an array, with header and trailer, to the given stream. ptrAt Object *ptrAt( int atIndex ) const; protected Returns a pointer to the element at the given index. reallocate void reallocate( sizeType newSize ); protected If delta is zero, reallocate gives an __EEXPANDFS error. Otherwise, reallocate tries to create a new array of size newSize (adjusted upwards to the nearest multiple of delta). The existing array is copied to the expanded array and then deleted. Unused elements in the new array are zeroed. An __ENOMEM error is invoked if there is insufficient memory for the reallocation. removeEntry void removeEntry( int loc ); protected Reduces the array by one element. Elements from index (loc + 1) upwards are copied to positions loc, (loc + 1), and so on. The original element at loc is lost. setData void setData( int loc, Object *data ); protected The given data replaces the existing element at the index loc. squeezeEntry void squeezeEntry( int squeezePoint ); protected Reduces the array by one element. As for removeEntry but squeezePoint is an index relative to the lower bound upperBound int upperBound() const; Returns the array's current upperbound. Friends ======================================================= ArrayIterator is a friend of AbstractArray - 40 - Array =========================================================================== Array array.h =========================================================================== ┌─────────────┐ ╔════════════╗ │AbstractArray├──╢ Array ║ └─────────────┘ ╚════════════╝ The instance class Array is derived from class AbstractArray. An Array object defines an array in which the ordering of the elements is arbitrary. That is, the element at index i of the array need have no relationship to the element at index i + 1. Array adds the functions add and addAt. While add stores a given object at the next free place in the array (expanding the array if necessary), addAt stores the object at a specified index. Example ======================================================= Source #include <iostream.h> #include <array.h> #include <strng.h> #include <assoc.h> int main() { Array a(2); String *s1 = new String("a string"); String *s2 = new String("another string"); Association *a1 = new Association(*s1,*s2); // Put some objects in the array a.add(*s1); a.add(*s2); a.add(*a1); // Print as a Container cout << "As a container:\n" << a << endl << endl; // Print as an Array cout << "As an array:\n"; a.printContentsOn(cout); // Print as elements - 41 - Array cout << "\nAs elements:\n"; for (int i = 0; i < a.arraySize(); ++i) cout << a[i] << endl; return(0); } Output As a container: Array { a string, another atring, Association { a string, another string } } As an array: Array { a string, another atring, Association { a string, another string } } As elements: a string another string Association { a string, another string} Member functions ======================================================= add virtual void add( Object& toAdd ); Adds the given object at the next available index at the end of an array. Adding an element beyond the upper bound leads to an overflow condition. If overflow occurs and delta is nonzero, the array is expanded (by sufficient multiples of delta bytes) to accommodate the addition. If delta is zero, overflow gives an error. addAt void addAt( Object& toAdd, int atIndex ); Writes the given object at the specified index. If that index is occupied, the previous object is deleted. If atIndex is beyond the upper bound, the array is expanded if delta is nonzero. If delta is zero, attempting to addAt beyond the upper bound gives an error. constructor Array( int anUpper, int aLower = 0, sizeType Delta = 0 ); - 42 - Array Constructs and "zeroes" an array by calling the base AbstractArray constructor. See also: AbstractArray::AbstractArray isA virtual classType isA() const; Returns arrayClass, the Arrays type ID. nameOf virtual char *nameOf() const; Returns "Array", the Array type ID string. =========================================================================== ArrayIterator abstarry.h =========================================================================== ┌─────────────────┐ ╔══════════════════╗ │ContainerIterator├──╢ ArrayIterator ║ └─────────────────┘ ╚══════════════════╝ Provides iterator functions to traverse objects of the class AbstractArray and its derived classes. ArrayIterator is a friend class of AbstractArray Member functions ======================================================= constructor ArrayIterator( const AbstractArray& toIterate ); Creates an iterator object for the given array. See also: restart current virtual Object& current(); Returns the object at the current index of the iterator. If the current index doesn't refer to a valid object, NOOBJECT is returned. operator ++ virtual Object& operator ++ (); virtual Object& operator ++ ( int ); See ContainerIterator operator ++ operator int() virtual operator int(); - 43 - ArrayIterator Conversion operator to test for end of iterator position. restart virtual void restart(); Sets the current index of the iterator to the first nonempty object in the array. =========================================================================== Association assoc.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Object ├──╢Association ║ └────────────┘ ╚════════════╝ The Association class provides a simple mechanism for associating two objects, known as the value object and the key object, in one Association type object. These combined objects are typically stored in a Dictionary type object, which provides member functions to retrieve the value when given the key, providing the basic tools for many data-retrieval applications. Member functions ======================================================= constructor Association( Object& key, Object& value ); Constructs an association object from the given key and value objects. constructor Association( const Association& a ); Copy constructor. hashValue virtual hashValueType hashValue() const; Returns the hash value of the association's key. See HashTable::hashValue for more details. isA virtual classType isA() const; Returns associationClass, the Association type ID. - 44 - Association isAssociation virtual int isAssociation() const; Returns 1 for association objects (and 0 for other object types). isEqual virtual int isEqual( const Object& toObject ) const; Returns 1 if toObject and the calling association have equal keys, otherwise returns 0. key Object& key() const; Returns the key object of the association. nameOf virtual char *nameOf() const; Returns "Association", the Association type ID string. printOn virtual void printOn( ostream& outputStream ) const; operator << is a Prints the association on the given output stream. friend of Object. printOn is really for internal use by the overloaded See page 87. operator <<. value Object& value() const; Returns the value object of the association. Example ======================================================= Source // File TASSOC.CPP: Illustrates the Association class #include <string.h> // For strlen() #include <strng.h> #include <assoc.h> #include <iostream.h> void identify(Object&); main() { char s1[21], s2[81]; // Read a key cout << "Enter a key: "; cin >> s1; cin.get(); // Eat newline - 45 - Association String str1(s1); identify(str1); // Read a value cout << "Enter a value: "; cin.getline(s2,81); s2[strlen(s2) - 1] = '\0'; String str2(s2); identify(str2); Association a1(str1,str2); identify(a1); Association a2 = a1; identify(a2); cout << "Equal: " << a1.isEqual(a2) << endl; } void identify(Object& o) { // Echo an object and its type cout << "Value: " << o << ", Object type: " << o.nameOf() << endl << endl; } Output Enter a key: class Value: class, Object type: String Enter a value: A group of related objects Value: A group of related objects, Object type: String Value: Association { class, A group of related objects } , Object type: Association Value: Association { class, A group of related objects } , Object type: Association Equal: 1 - 46 - Bag =========================================================================== Bag bag.h =========================================================================== ┌────────────┐ ╔════════════╗ ┌────────────┐ │ Collection ├──╢ Bag ╟──┤ Set │ └────────────┘ ╚════════════╝ └────────────┘ A Bag is an unordered collection that may contain more than one of the same object. Bag also provides the base class for Set. Unlike Bags, Sets can contain only one copy of a any given object. Member functions ======================================================= add virtual void add( Object& toAdd ); Adds the given object at the next available index at the end of an array. Adding an element beyond the upper bound leads to an overflow condition. If overflow occurs and delta is nonzero, the array is expanded (by sufficient multiples of delta bytes) to accommodate the addition. If delta is zero, overflow gives an error. constructor Bag( sizeType bagSize = DEFAULT_BAG_SIZE ); Constructs an empty bag. bagSize represents the initial number of slots allocated. detach virtual void detach( Object& toDetach, DeleteType dt = NoDelete ); See Array::detach. findMember virtual Object& findMember( Object& toFind ) const; Returns the given object if found, otherwise returns NOOBJECT. firstThat virtual Object& firstThat( condFuncType testFuncPtr, void *paramList ) const; See also: Container::firstThat, Object::firstThat flush void flush( DeleteType dt = DefDelete ); - 47 - Bag Removes all the elements from the bag without destroying the bag. The value of dt determines whether the elements themselves are destroyed. By default, the ownership status of the bag determines their fate, as explained in the detach member function. You can also set dt to Delete and NoDelete. See also: detach forEach void forEach( void ( *actionFuncPtr)(Object& o, void *), void *args ); See also: Container::forEach getItemsInContainer countType getItemsInContainer() const; Returns the number of items in the bag. hasMember virtual int hasMember( const Object& obj ) const; Returns 1 if the given object is found in the bag, otherwise returns 0. initIterator ContainerIterator& initIterator() const; Creates and returns an iterator for this bag. See also: ContainerIterator class isA virtual classType isA() const; Returns bagClass the Bag type ID. isEmpty int isEmpty() const; Returns 1 if a container has no elements; otherwise returns 0. lastThat virtual Object& lastThat( condFuncType testFuncPtr, void *paramList ) const; Returns a reference to the last object in the container that satisfies a given condition. You supply a testFuncPtr that returns true for a certain condition. You can pass arbitrary arguments via the paramList argument. NOOBJECT is returned if no object in the container meets the condition. Note that you are not involved directly with iterators: firstThat and - 48 - Bag lastThat create their own internal iterators, so you can simply treat them as "search" functions. See also: firstThat, Object::firstThat, Container::lastThat nameOf virtual char *nameOf() const; Returns "Bag", the Bag type ID string. ownsElements int ownsElements(); void ownsElements( int del ); See TShouldDelete::ownsElements =========================================================================== BaseDate ldate.h =========================================================================== ┌────────────┐ ╔════════════╗ ┌────────────┐ │ Sortable ├──╢ BaseDate ╟──┤ Date │ └────────────┘ ╚════════════╝ └────────────┘ BaseDate is an abstract class derived from Sortable that provides basic date manipulation functions. Member functions ======================================================= constructor BaseDate(); protected Creates a BaseDate object with the current system date. constructor BaseDate( unsigned char M, unsigned char D, unsigned Y ); protected Creates a BaseDate object with the given month, day, and year. constructor BaseDate( const BaseDate& BD ); protected Copy constructor. Day unsigned Day() const; Returns the day of the month. - 49 - BaseDate hashValue virtual hashValueType hashValue() const; Returns the hash value of the date object. See HashTable::hashValue for more details. isA virtual classType isA() const = 0; A pure virtual function to return a classtype ID (to be defined in derived classes). isEqual virtual int isEqual( const Object& testDate ) const; Returns 1 if the object represents the same date as testDate. Otherwise returns 0. isLessThan virtual int isLessThan( const Object& testDate ) const; Returns 1 if the object precedes testDate on the calendar. Month unsigned Month() const; Returns the month. nameOf virtual char *nameOf() const = 0; Pure virtual function to be defined by derived classes to return their object ID string. printOn virtual void printOn( ostream& outputStream ) const = 0; operator << is a Pure virtual function to be defined in derived classes friend of Object. to print the date object on the given stream. printOn See page 87. is for internal use by the overloaded operator <<. SetDay void SetDay( unsigned char D ); Sets the day to D. SetMonth void SetMonth( unsigned char M ); Sets the month to M. SetYear void SetYear( unsigned Y ); Sets the year to Y. - 50 - BaseDate Year unsigned Year() const; Returns the year. =========================================================================== BaseTime ltime.h =========================================================================== ┌────────────┐ ╔════════════╗ ┌────────────┐ │ Sortable ├──╢ BaseTime ╟──┤ Time │ └────────────┘ ╚════════════╝ └────────────┘ BaseTime is an abstract class derived from Sortable that provides basic time manipulation functions. Member functions ======================================================= constructor BaseTime(); protected Creates a BaseTime object with the current system time. constructor BaseTime( const BaseTime& BT ); protected Copy constructor. constructor BaseTime( unsigned char H, unsigned char M = 0, unsigned char S = 0, unsigned char HD = 0 ); protected Creates a BaseTime object with the given hour, minutes, seconds, and hundredths of seconds. hashValue virtual hashValueType hashValue() const; Returns the hash value of the BaseTime object. See HashTable::hashValue for more details. hour unsigned hour() const; Returns the hour. hundredths unsigned hundredths() const; - 51 - BaseTime Returns the hundredths of a second. isA virtual classType isA() const = 0; Pure virtual function for a derived class to return its class ID. isEqual virtual int isEqual( const Object& testTime ) const; Returns 1 if this object equals testTime; otherwise returns 0. isLessThan virtual int isLessThan( const Object& testTime ) const; Returns 1 if this object is less than testTime; otherwise returns 0 . minute unsigned minute() const; Returns the minute. nameOf virtual char *nameOf() const = 0; Pure virtual function to be defined by derived classes to return their object ID string. printOn virtual void printOn( ostream& outStream ) const = 0; operator << is a Pure virtual function to be defined in derived classes friend of Object. to print the time object on the given stream. printOn See page 87. is for internal use by the overloaded operator <<. second unsigned second() const; Returns the seconds. setHour void setHour( unsigned char H ); Sets the hour to H. setHundredths void setHundredths( unsigned char HD ); Sets the hundredths of a second to HD. setMinute void setMinute( unsigned char M ); Sets the minutes. - 52 - BaseTime setSecond void setSecond( unsigned char S ); Sets the seconds. =========================================================================== Btree btree.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Collection ├──╢ Btree ║ └────────────┘ ╚════════════╝ The class Btree, derived from Collection, implements the B-tree, a popular data structure offering efficient storage and retrieval with large, dynamic volumes of data. (A detailed account of Turbo C++ development of B-tree theory is beyond the scope of this manual: see BTREE.CPP and D. E Knuth's The Art of Computer Programming, Volume 3, 6.2.3.). Btree makes use of several auxiliary, noncontainer friend classes: Node, Item, InnerNode, and LeafNode (the last two being derived from Node). You can study these in btree.h. Here, we will just outline the members of the Btree class, which should suffice for most applications. Member functions ======================================================= add void add( Object& ); Add the given object to the B-tree. constructor Btree( int ordern = 3 ); Creates a B-tree of order ordern (default order is 3). decrNofKeys void decrNofKeys(); protected Decrements the itemsInContainer data member detach void detach( Object& toDetach, DeleteType dt = NoDelete ); - 53 - Btree Removes the given object from the B-tree. The fate of the removed object depends on the argument dt. See TShouldDelete for details. findMember virtual Object& findMember( const Object& toFind ) const; Returns the given object if found, otherwise returns NOOBJECT. flush void flush( DeleteType dt = DefDelete ); Flushes (empties) the B-tree. The fate of the removed objects depends on the argument dt. See TShouldDelete for details. hasMember virtual int hasMember( const Object& obj ) const; Returns 1 if the given object is found in the B-tree, otherwise returns 0. hashValue virtual hashValueType hashValue() const; Returns the hash value of this B-tree. See HashTable::hashValue for more details. i_add long i_add( const Object& obj ); protected Adds the given object to the tree and returns the index in the tree at which the object was inserted. incrNofKeys void incrNofKeys(); protected Increments the itemsInContainer data member initIterator virtual ContainerIterator& initIterator() const; Creates an iterator for this B-tree. See also: Container::initIterator isA virtual classType isA() const; Returns btreeClass, the Btree class ID isEqual virtual int isEqual( const Object& testObject ) const; Returns 1 if testObject is the same as this object. - 54 - Btree nameOf virtual char *nameOf() const; Returns "Btree", the Btree class ID string operator [] Object& operator[]( long i ) const; Returns the root at index i order int order(); Returns the order of the B-tree. printOn virtual void printOn( ostream& outputStream ) const; operator << is a Sends the formatted B-tree data to the given output friend of Object. stream. printOn is for internal use by the overloaded See page 87. operator <<. rank long rank( const Object& obj ) const; Returns the rank of the given object in the B-tree. Friends ======================================================= Node, InnerNode, and LeafNode are friends of Btree. =========================================================================== BtreeIterator btree.h =========================================================================== ┌─────────────────┐ ╔══════════════════╗ │ContainerIterator├──╢ BtreeIterator ║ └─────────────────┘ ╚══════════════════╝ The class BtreeIterator is derived from ContainerIterator. Its members follow the same scheme as those for the other container iterators. - 55 - BtreeIterator Member functions ======================================================= constructor BtreeIterator( const Btree& toIterate ); See ContainerIterator constructor current virtual Object& current(); See ContainerIterator::current operator ++ virtual Object& operator ++(); virtual Object& operator ++( int ); See ContainerIterator::operator ++ operator int virtual operator int(); Conversion operator to test for end of iterator position. restart virtual void restart(); See ContainerIterator::restart - 56 - Collection =========================================================================== Collection collect.h =========================================================================== ┌─────────────┐ ┌─┤AbstractArray│ │ └─────────────┘ │ ┌─────────────┐ ├─┤ HashTable │ │ └─────────────┘ ┌────────────┐ ╔════════════╗ │ ┌─────────────┐ │ Container ├──╢ Collection ╟─┼─┤ List │ └────────────┘ ╚════════════╝ │ └─────────────┘ │ ┌─────────────┐ ├─┤ DoubleList │ │ └─────────────┘ │ ┌─────────────┐ ├─┤ Bag │ │ └─────────────┘ │ ┌─────────────┐ └─┤ Btree │ └─────────────┘ Collection is an abstract class derived from the abstract class Container. This means that although Collection is more specialized than Container, it still cannot be used directly for creating useful objects but exists only as a further stepping stone towards usable, derived instance classes. Collection inherits five pure virtual functions (flush, initIterator, isA, nameOf and getItemsInContainer), that simply await definitions down the road by derived instance classes. Collection extends the functionality of Container in several areas by adding both virtual and pure virtual member functions. The extra pure virtual functions are add and detach. Instance classes ultimately derived from Collection, therefore, will need to provide appropriate member functions for adding and removing elements. The other (non-pure) virtual member functions added by Collection are destroy, hasMember, and findMember. The last two provide the key difference between Collection and Container. A Collection-derived object can determine if any given object is a member (with - 57 - Collection hasMember) and, by using an iterator, can locate a member object within the collection (with findMember). The offspring of Collection refine these access methods in various ways, and add other functions. In most applications, you will be dealing directly with a particular derived class of Collection, chosen to match your needs: sorted and unsorted arrays, hash tables, bags, sets, dictionaries, and single and double lists. However, it is useful to have a feel for how these instance classes build up from abstract classes, and why it is useful to have intermediate abstract classes. Member functions ======================================================= add virtual void add( Object& o ) = 0; Pure virtual function to be defined in derived classes to add an object to a collection. constructor Uses the Container base constructor. destroy void destroy( const Object& o ); Removes an object from a Collection. Whether the object itself is destroyed or not depends on the ownership status of the collection. If the collection currently owns the object, the object will be destroyed, otherwise the object survives. destroy is implemented with detach( o, DefDelete ); See also: TShouldDelete::ownsElements detach virtual void detach( Object& o, DeleteType dt = NoDelete) = 0; Pure virtual function to be defined in derived classes to remove an object from a collection. The destruction of the object depends both on the ownership status and the value (Delete, NoDelete, or DefDelete) passed via the dt argument. See also: destroy, TShouldDelete::ownsElements findMember virtual Object& findMember( const Object& testObject ) const; - 58 - Collection Returns the test object if it is in the collection, otherwise returns NOOBJECT. hasMember virtual int hasMember( const Object& o ) const; Returns 1 if the collection contains the given object. =========================================================================== Container contain.h =========================================================================== ┌────────────┐ ┌─┤ Collection │ │ └────────────┘ ┌────────────┐ ╔════════════╗ │ ┌────────────┐ │ Object ├──╢ Container ╟─┼─┤ Stack │ └────────────┘ ╚════════════╝ │ └────────────┘ │ ┌────────────────────┐ ├─┤ PriorityQueue │ │ └────────────────────┘ │ │ ┌────────────┐ ┌────────────┐ └─┤ Deque ├─┤ Queue │ └────────────┘ └────────────┘ The abstract class Container, derived directly from Object, is the base for all the container classes. Container has a second pure virtual base class (not shown) called TShouldDelete. Container provides the following functionality: 1. A container can store objects of other classes, known as elements or items. (The objects in a container are sometimes called "members" of the container, but this usage can lead to ambiguities in C++.) A container can flush itself by removing all its elements. 2. A container can determine the number of objects it holds. Empty containers are allowed. 3. Container is also derived from TShouldDelete (multiple inheritance), which lets you control the ownership of a container's elements. By default, a container owns its elements, meaning that it will - 59 - Container destroy them when its destructor is called or when it is flushed. 4. A container can create external iterators, objects of type ContainerIterator, which can be used to traverse the container, element by element. With external iterators, you need to handle the scanning of the elements yourself. Other iterators, known as internal iterators, are generated automatically by certain member functions. These do their own loop tests and can perform arbitrary actions on each element (forEach). Member functions are also available for scanning the container until a certain condition is satisfied (firstThat, lastThat). 5. A container can test if it is equal to another container. 6. A container can display its elements on streams in a formatted way. A printOn function is provided from which the usual overloaded << output operator can be obtained. Strictly speaking, some of the above member functions are pure virtual functions that need to be defined in derived classes. See Collection class for a more detailed discussion. Specialized containers are derived to two ways: directly derived are the classes Stack, PriorityQueue, and Deque (from which Queue is derived). Derived indirectly via another abstract class, Collection, are AbstractArray, HashTable, Bag, Btree, List, and DoubleList. itemsInContainer countType itemsInContainer; protected Holds the current number of elements in the container. See also: getItemsInContainer Member functions ======================================================= constructor Container(); Creates an empty container. - 60 - Container firstThat virtual Object& firstThat( condFuncType testFuncPtr, void *paramList ) const; Returns a reference to the first object in the container that satisfies a given condition. You supply a testFuncPtr that returns true for a certain condition. You can pass arbitrary arguments via the paramList argument. NOOBJECT is returned if no object in the container meets the condition. Note that you are not involved directly with iterators: firstThat and lastThat create their own internal iterators, so you can simply treat them as "search" functions. See also: lastThat, Object::firstThat flush virtual void flush( DeleteType dt = DefDelete ) = 0; A pure virtual function to be defined in derived classes. Flushing means removing all the elements from the container without destroying it. The value of dt determines whether the elements themselves are destroyed. By default, the ownership status of the container determines their fate. You can also set dt to Delete and NoDelete. See also: TShouldDelete::ownsElements forEach virtual void forEach( iterFuncType actionFuncPtr, void *args ); forEach creates an internal iterator to execute the given action function for each element in the container. The args argument lets you pass arbitrary data to the action function. getItemsInContainer virtual countType getItemsInContainer() const = 0; Pure virtual function to be defined by derived classes to return the number of elements in a container. hashValue virtual hashValueType hashValue() const = 0; A pure virtual function to be defined by derived classes to return the hash value of an object. See HashTable::hashValue for more details. initIterator virtual ContainerIterator& initIterator() const = 0; - 61 - Container Pure virtual function to be defined in derived classes to initialize an external container iterator. isA virtual classType isA() const = 0; Pure virtual function to be defined in derived classes to return their class ID. isEmpty virtual int isEmpty() const = 0; Pure virtual function to be defined in derived classes. Returns 1 if a container has no elements; otherwise returns 0. isEqual virtual int isEqual( const Object& testObject ) const; Returns 1 if the testObject is a container of the same type and size as this container, and with the same objects in the same order. Otherwise returns 0. lastThat virtual Object& lastThat( condFuncType testFuncPtr, void *paramList ) const; Returns a reference to the last object in the container that satisfies a given condition. You supply a testFuncPtr that returns true for a certain condition. You can pass arbitrary arguments via the paramList argument. NOOBJECT is returned if no object in the container meets the condition. Note that you are not involved directly with iterators: firstThat and lastThat create their own internal iterators, so you can simply treat them as "search" functions. See also: firstThat, Object::firstThat nameOf virtual char *nameOf() const = 0; Pure virtual function to be defined by derived classes to return their object type ID string (usually the unique class name). printHeader virtual void printHeader( ostream& outputStream ) const; Sends a standard header for containers to the output stream (called by printOn). See also: printOn, printSeparator, printTrailer - 62 - Container printOn virtual void printOn( ostream& outputStream ) const; operator << is a Sends a formatted representation of the container to friend of Object. the given output stream. printOn is for internal use by See page 87. the overloaded operator <<. See also: printHeader, printSeparator, printTrailer printSeparator virtual void printSeparator( ostream& outputStream ) const; Sends to the output stream a separator (comma) between elements in a container (called by printOn). See also: printOn, printHeader, printTrailer printTrailer virtual void printTrailer( ostream& outputStream ) const; Sends to the output stream a standard trailer (a closing brace) for a container (called by printOn). See also: printOn, printHeader, printSeparator Friends ======================================================= ContainerIterator is a friend of Container. - 63 - ContainerIterator =========================================================================== ContainerIterator contain.h =========================================================================== ┌──────────────────┐ ┌─┤HashTableIterator │ │ └──────────────────┘ ╔═════════════════╗ │ ┌──────────────────┐ ║ContainerIterator╟─┼─┤ ListIterator │ ╚═════════════════╝ │ └──────────────────┘ │ ┌──────────────────┐ ├─┤DoubleListIterator│ │ └──────────────────┘ │ ┌──────────────────┐ ├─┤ BtreeIterator │ │ └──────────────────┘ │ ┌──────────────────┐ └─┤ ArrayIterator │ └──────────────────┘ ContainerIterator is an abstract class declared as a friend of Container. Container classes have initIterator member functions that create ContainerIterator-derived objects. These provide the basic mechanisms for traversing the elements in a container: incrementing through the container; returning positional information; testing for conditions, and so on. The member functions for ContainerIterator are all pure virtual and are defined in derived classes. See page 11 for more on the ContainerIterator hierarchy. Member functions ======================================================= current virtual Object& current() = 0; Pure virtual function to be defined in derived classes to return the current element. If the current element is empty or invalid, NOOBJECT is returned. operator int virtual operator int() = 0; Pure virtual function to be defined by derived classes to provide a conversion operator to test for end of iteration condition. - 64 - ContainerIterator operator ++ virtual Object& operator ++() = 0; virtual Object& operator ++( int ) = 0; Advances the iterator one position in the container. The first version returns the object referred to before incrementing; the second version returns the object referred to after incrementing. The int argument is a dummy used to distinguish the two operators (see the section on Operator Overloading in the Programmer's Guide). restart virtual void restart() = 0; Pure virtual function to be refined in derived classes to set the current index of the iterator to the first nonempty element in the container. =========================================================================== Date ldate.h =========================================================================== ┌────────────┐ ╔════════════╗ │ BaseDate ├──╢ Date ║ └────────────┘ ╚════════════╝ The Date instance class is a direct descendant of the abstract class BaseDate, defining a printOn function. You can vary Date for different national conventions without disturbing BaseDate. Member functions ======================================================= constructor Date(); Calls the BaseDate constructor to create a date object with today's date. constructor Date( unsigned char M, unsigned char D, unsigned Y ); Calls the BaseDate constructor to create a date object with the given date. constructor Date( const Date& aDate ); - 65 - Date Copy constructor. isA virtual classType isA() const; Returns dateClass, the Date class ID. nameOf virtual char *nameOf() const; Returns "Date", the Date class ID string. printOn virtual void printOn( ostream& outputStream ) const; operator << is a Sends a formatted date to the given output stream. The friend of Object. format is full month name, day, year, for example See page 87. January 1, 1990. printOn is really for internal use by the overloaded operator <<. =========================================================================== Deque deque.h =========================================================================== ┌────────────┐ ╔════════════╗ ┌────────────┐ │ Container ├──╢ Deque ╟─┤ Queue │ └────────────┘ ╚════════════╝ └────────────┘ The instance class Deque (pronounced "deck"), derived from Container, implements a double-ended queue so it is one of the sequence classes. Objects can be examined, inserted, and removed at both the left and the right ends but nowhere else. You can use the member functions peekLeft and peekRight to examine the objects currently at the left and the right ends. putLeft and putRight insert objects at the ends. The getLeft and getRight members also access the end objects but detach them from the deque. The fate of the objects removed from the deque is determined by the same ownership and DeleteType considerations discussed in the TShouldDelete class (recall that TShouldDelete is a virtual base class for Container). Deque also acts as the base class for Queue. - 66 - Deque Example ======================================================= Source #include <deque.h> #include <strng.h> main() { Deque d; String *s1 = new String("one"); String *s2 = new String("two"); String *s3 = new String("three"); String *s4 = new String("four"); // Populate the deque d.putLeft(*s1); d.putRight(*s2); d.putLeft(*s3); d.putRight(*s4); // Print to cout cout << "As a container:\n" << d << endl; // Empty to cout cout << "As a Deque:\n"; while (!d.isEmpty()) { cout << d.getLeft() << endl; } // Should be empty cout << "\nShould be empty:\n" << d; } Output As a container: Deque { three, one, two, four } As a Deque: three one two four Should be empty: - 67 - Deque Deque { } Member functions ======================================================= flush virtual void flush( DeleteType dt = DefDefault ); Flushes (empties) the deque without destroying it. The fate of any objects thus removed depends on the current ownership status and the value of the dt argument. See also: TShouldDelete::ownsElements getItemsInContainer virtual countType getItemsInContainer() const; Returns the number of items in the deque. getLeft Object& getLeft(); Returns the object at the left end and removes it from the deque. Returns NOOBJECT if the deque is empty. See also: TShouldDelete class getRight Object& getRight(); As for getLeft, except that the right end of the deque is returned. See also: getLeft initIterator virtual ContainerIterator& initIterator() const; Initializes an iterator for the deque. See also: Container::initIterator isA virtual classType isA() const; Returns dequeClass, the Deque class ID. isEmpty virtual int isEmpty() const; Returns 1 if a container has no elements; otherwise returns 0. nameOf virtual char *nameOf() const; - 68 - Deque Returns "Deque", the Deque class ID string. peekLeft Object& peekLeft() const; Returns the object at the left end (head) of the deque. The object stays in the deque. peekRight Object& peekRight() Returns the object at the right end (tail) of the deque. The object stays in the deque. putLeft void putLeft( Object& obj ); Adds (pushes) the given object at the left end (head) of the deque. putRight void putRight(Object& obj) Adds (pushes) the given object at the right end (tail) of the deque. =========================================================================== Dictionary dict.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Set ├──╢ Dictionary ║ └────────────┘ ╚════════════╝ A dictionary is a special collection of Association type objects. The instance class Dictionary is derived from Collection via Bag and Set, implying that no duplicate association objects are allowed in a dictionary. Dictionary overrides the add function and adds a lookup function to the members inherited from Set. lookup allows you to retrieve the value object of an association stored in the dictionary if you supply the key. Member functions ======================================================= add virtual void add( Object& assoc ); - 69 - Dictionary Adds the given association (assoc) to the dictionary. If the given argument is not of type Association, a runtime error occurs. constructor Dictionary( unsigned sz = DEFAULT_HASH_TABLE_SIZE ); Invokes the base Set constructor to create an empty dictionary of size sz. isA virtual classType isA() const; Returns dictionaryClass, the Dictionary class ID. lookup Association& lookup( const Object& toLookUp ) const; Returns the association matching the toLookUp key. If no match is found, NOOBJECT is returned. nameOf virtual char *nameOf() const; Returns "Dictionary", the Dictionary class ID string. =========================================================================== DoubleList dbllist.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Collection ├──╢ DoubleList ║ └────────────┘ ╚════════════╝ The instance class DoubleList, derived from Collection, implements the classical doubly-linked list data structure (see D. E Knuth's The Art of Computer Programming, Volume 1, 2.2.5). Briefly, each node object of a doubly-linked list has two links, one pointing to the next node and one pointing to the previous node. The extreme nodes are called the head and the tail. As with the Deque class, you can examine, add, and remove objects at either end of the list. - 70 - DoubleList Member functions ======================================================= add virtual void add( Object& toAdd ); Add the given object at the beginning of the list. addAtHead void addAtHead( Object& toAdd ); Adds the given object at the beginning (head) of the list. addAtTail void addAtTail( Object& toAdd ); Adds the given object at the end (tail) the list. constructor DoubleList(); Creates a new, empty doubly-linked list. destroyFromHead void destroyFromHead( const Object& toDestroy ); Detaches the first occurrence of the given object encountered by searching from the beginning of the list. The object is destroyed only if it is owned by the list. destroyFromTail void destroyFromTail( const Object& toDestroy ); Detaches the first occurrence of the given object encountered by searching from the tail of the list towards the head. The object is destroyed only if it is owned by the list. detach virtual void detach( Object& toDetach, DeleteType dt = NoDelete ); Calls detachFromHead( toDetach, dt); detachFromHead void detachFromHead( const Object& toDetach, DeleteType dt = NoDelete ); Removes the first occurrence of the given object encountered by searching from the beginning of the list. The dt argument determines if the detached object is itself destroyed. See TShouldDelete for details. - 71 - DoubleList detachFromTail void detachFromTail( const Object& toDetach, DeleteType dt = NoDelete ); Removes the first occurrence of the object starting at the tail of the list and scanning towards the head. The dt argument determines if the detached object is itself destroyed. See TShouldDelete for details. flush virtual void flush( DeleteType dt = DefDelete); Flushes (empties) the list without destroying it. The fate of the objects thus removed is determined by the dt argument as explained at TShouldDelete. The default value of dt means that the removed objects will be destroyed only if the list owns these objects. See also: TShouldDelete::ownsElements initIterator virtual ContainerIterator& initIterator() const; Creates and returns a forward (from head to tail) iterator for the list. isA virtual classType isA() const; Returns doubleListClass, the DoubleList class ID. nameOf virtual char *nameOf() const; Returns "DoubleList", the DoubleList class ID string. peekAtHead Object& peekAtHead() const; Returns the object at the head of the list (without removing it). peekAtTail Object& peekAtTail() const; Returns the object at the tail of the list (without removing it). - 72 - DoubleList Friends ======================================================= DoubleListIterator is a friend of DoubleList =========================================================================== DoubleListIterator dbllist.h =========================================================================== ┌─────────────────┐ ╔══════════════════╗ │ContainerIterator├──╢DoubleListIterator║ └─────────────────┘ ╚══════════════════╝ DoubleListIterator, derived from ContainerIterator, implements the special iterators for traversing doubly-linked lists in either direction. This class adds overloading of the pre- and postdecrement operator - - to allow reverse iteration. For more details on iterators, see ContainerIterator, and DoubleList::initIterator. Member functions ======================================================= constructor DoubleListIterator(const DoubleList& toIterate, int atHead = 1); Creates an iterator for the given list. The iterator will begin at the head of the list if atHead is 1 , otherwise it starts at the tail. current virtual Object& current(); Returns the object at the current index of the iterator. If the current index exceeds the upper bound, NOOBJECT is returned. operator ++ virtual Object& operator ++ ( int ); virtual Object& operator ++ (); See ContainerIterator operator ++ operator - - Object& operator - - ( int ); Object& operator - - (); - 73 - DoubleListIterator Moves the iterator back one position in the list. The object returned is either the current object (postdecrement) or the object at the new position (predecrement), or NOOBJECT if no valid object at the relevant position. The first version gives postdecrement, the second gives predecrement. The int argument is a dummy serving only to distinguish the two operators. operator int virtual operator int(); Conversion operator to test for the end of an iteration condition. restart virtual void restart(); Moves the iterator back to its starting position at the head of the list. See also: DoubleListIterator constructor =========================================================================== Error object.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Object ├──╢ Error ║ └────────────┘ ╚════════════╝ The class Error is a special instance class derived from Object. There is just one instance of class Error, namely theErrorObject. Pointing to this global object is the static object pointer Object::ZERO. NOOBJECT is defined as *(Object::ZERO) in object.h. The operator Object::operator new returns a pointer to theErrorObject if an attempt to allocate an object fails. You may test the return value of the new operator against Object::ZERO to see whether the allocation failed. NOOBJECT is rather like a null pointer, but serves the vital function of occupying empty slots in a container. For example, when an Array object is created (not to be confused with a traditional C array), each of its elements will initially contain NOOBJECT. - 74 - Error Member functions ======================================================= delete void operator delete(void *); Invokes a runtime error if an attempt to delete the Error object is detected. isA virtual classtype isA() const; Returns errorClass, the Error class ID. isEqual virtual int isEqual( const Object& testObject const ); Returns 1 if the test object is the Error object. nameOf virtual char *nameOf() const; Returns the Error class ID string. printOn virtual void printOn(ostream& outputStream ) const; operator << is a Prints the string "Error\n" on the given stream. friend of Object. printOn is for internal use by the overloaded operator See page 87. <<. =========================================================================== HashTable hashtbl.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Collection ├──╢ HashTable ║ └────────────┘ ╚════════════╝ The instance class HashTable provides an implementation of an unordered collection in which objects are added and retrieved via a hashing function. A hash table provides a fixed array with size slots (usually a prime number), one for each possible hash value modulo size. A hashing function computes the hash value for each object (or a key part of that object) to be added, and this determines the slot to which the new object is assigned. - 75 - HashTable For each containable object of class X, the member function X::HashValue returns a value (of type hashValueType) between 0 and 65535, which is as "unique" as possible. This "raw" hash value is reduced modulo size. We'll use the term hash value to refer to this reduced value in the range 0 to size - 1. This hash value serves as an index into the hash table. The internal organization of the table is hidden, but it may help you to consider the slots as pointers to lists. It should be clear that if you want to store more than size objects, the hash value cannot be unique for each object. So two cases arise when an object is added: if the slot is empty, a new list is assigned to the slot and the object is stored in the list; if the slot is already occupied by an object with the same hash value (known as a collision), the new object is stored in the existing list attached to the slot. When it comes to locating an object, the hashing function computes its hash value to access the appropriate slot. If the slot is empty, NOOBJECT is returned, otherwise a List::findMember call locates the object. Choosing the best HashValue function and table size is a delicate compromise between avoiding too many collisions and taking up too much memory. (Other hashing techniques are available, but the modulo prime method is the most common. For more on hash table theory, see D. E. Knuth's The Art of Computer Programming, Volume 3, 6.4.). Hashing is widely used by compilers to maintain symbol tables. Member functions ======================================================= add virtual void add( Object& objectToAdd ); Adds the given object to the hash table. constructor HashTable( sizeType aPrime = DEFAULT_HASH_TABLE_SIZE ); Creates an empty table. The aPrime argument is a prime number used in the hashing function (the default is defined in resource.h). detach - 76 - HashTable virtual void detach( Object& objectToDetach, DeleteType dt = NoDelete ); Removes the given object from the hash table. Whether the object itself is destroyed or not depends on the dt argument, as explained in TShouldDelete::ownsElements. findMember virtual Object& findMember( const Object& testObject ) const; Returns the target object if found, otherwise returns NOOBJECT. flush virtual void flush( DeleteType dt = DefDelete ); Removes all the elements from the table without destroying it. The value of dt determines whether the elements themselves are destroyed. By default (dt = DefDelete), the ownership status of the table determines the fate of all its elements, as explained in TShouldDelete::ownsElements. You can set dt to Delete to force destruction of the flushed elements regardless of ownership. If dt is set to NoDelete, the flushed elements will survive regardless of ownership. See also: TShouldDelete::ownsElements hashValue virtual hashValueType hashValue() const; Returns the raw hash value of this table. This must not be confused with the hash values calculated by the hash table for each of the objects it stores. When an object x of class X is added or retrieved from a hash table h, the raw hash value used is x.hashValue(). The true hash value (usually modulo size) is obtained from the hash table object via h.getHashValue( x ). Only classes with a proper hashValue member function can provide objects for storage in a hash table. All standard Object- derived classes in the library have meaningful hashing functions provided. For example, BaseDate::hashValue (unless overridden) returns the value YY + MM + DD from which the (private) member function HashTable::getHashValue computes a hash value (using mod size). It is this value that governs the hash table's add, findMember, and detach operations. initIterator virtual ContainerIterator& initIterator() const; - 77 - HashTable Creates and returns an iterator for the hash table. See Container::initIterator for more details. isA virtual classType isA() const; Returns hashTableClass, the HashTable class ID. nameOf virtual char *nameOf() const; Returns "HashTable", the HashTable class ID string. Friends ======================================================= HashTableIterator is a friend of HashTable =========================================================================== HashTableIterator hashtbl.h =========================================================================== ┌─────────────────┐ ╔══════════════════╗ │ContainerIterator├──╢HashTableIterator ║ └─────────────────┘ ╚══════════════════╝ HashTableIterator is an instance class providing iterator functions for HashTable objects. Since hash values are stored in an array, hash table iterators use the array iterator mechanism. See ContainerIterator for a detailed discussion of iterators. Member functions ======================================================= constructor HashTableIterator( const Array& toIterate ); See ContainerIterator constructor current virtual operator Object& current(); See ContainerIterator::current operator int virtual operator int(); Conversion operator to test for end of iterator position. - 78 - HashTableIterator operator ++ virtual Object& operator ++ ( int ); virtual Object& operator ++ (); See ContainerIterator::operator ++ restart virtual void restart() See ContainerIterator::restart =========================================================================== List list.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Collection ├──╢ List ║ └────────────┘ ╚════════════╝ The instance class List, derived from Collection, implements a linear, linked list. Lists are unordered collections in which objects are linked in one direction only to form a chain. You can usually add objects only at the start of a list but any object can be removed from a list. You can traverse a list (from head to tail) with an iterator to access the objects sequentially. List has an internal private class ListElement providing memory management and other functions for the pairs of pointers (to object and to next element) that constitute the elements of a List object. (For more on list theory, see Sedgwick's Algorithms and Knuth's The Art of Computer Programming, Volume 1, 2.2). Member functions ======================================================= add void add( Object& toAdd ); Adds the given object at the head of the list. The added object becomes the new head. constructor List(); Creates an empty list. detach - 79 - List virtual void detach( Object& toDetach, DeleteType dt = NoDelete ); Removes the given object from the list. Whether the object itself is destroyed or not depends on the dt argument, as explained in TShouldDelete::ownsElements. flush virtual void flush( DeleteType dt = DefDelete ); Removes all the objects from the list without destroying it. The value of dt determines whether the objects themselves are destroyed. By default (dt = DefDelete), the ownership status of the list determines the fate of its elements, as explained in TShouldDelete::ownsElements. You can set dt to Delete to force destruction of the flushed objects regardless of ownership. If dt is set to NoDelete, the flushed objects will survive regardless of ownership. See also: TShouldDelete::ownsElements hashValue virtual hashValueType hashValue() const; Returns the hash value of this list. See HashTable::hashValue for more details. initIterator virtual ContainerIterator& initIterator() const; See Container::initIterator isA virtual classType isA() const; Returns listClass the List class ID. nameOf virtual char *nameOf() const; Returns "List", the List class ID string. peekHead Object& peekHead() const; Returns the object at the head of the list. Friends ======================================================= ListIterator is a friend of List and ListElement. - 80 - ListIterator =========================================================================== ListIterator list.h =========================================================================== ┌─────────────────┐ ╔══════════════════╗ │ContainerIterator├──╢ ListIterator ║ └─────────────────┘ ╚══════════════════╝ ListIterator is an instance class derived from ContainerIterator providing iterator functions for List objects. See ContainerIterator for a discussion of iterators. Member functions ======================================================= constructor ListIterator( const List& toIterate ); Creates an iterator for the given list. The starting and current elements are set to the first element of the list. See ContainerIterator constructor for details. current virtual Object& current(); See ContainerIterator::current operator ++ virtual Object& operator ++ ( int ); virtual Object& operator ++ (); See ContainerIterator::operator ++ operator int virtual operator int(); Conversion operator to test for end of iterator position. restart virtual void restart() See ContainerIterator::restart - 81 - MemBlocks =========================================================================== MemBlocks memmgr.h =========================================================================== ╔════════════╗ ║ MemBlocks ╟ ╚════════════╝ The classes MemBlocks and MemStack in memmgr.h offer specialized memory management not only for the container classes but for other applications. Detailed knowledge of their operations is not needed for normal container applications. If you are planning your own advanced memory management schemes, you should first study memmgr.h and MEMMGR.CPP. MemBlocks is a noncontainer, instance class, providing fixed-block memory allocations. Large, dynamic lists and trees need to allocate and free their node blocks as quickly as possible. MemBlocks offers more efficient memory management than the standard heap manager for this kind of operation. The MemBlock constructor takes two arguments: block size and number of blocks. These determine the size of the internal blocks that are allocated as needed using the normal run-time library allocation functions. A free list of blocks is maintained and the internal blocks are not released until the MemBlock object is destroyed. The following example illustrates the use of MemBlocks with a simplified Node class: class Node { Node *next; Object *obj; static MemBlocks memBlocks; void *operator new( size_t sz ) { return memBlocks.allocate ( sz); } void operator delete( void * blk ) { memBlocks.free ( blk ); } ... }; CAUTION: If you derive a class from a class that does its own memory management as in the Node example above, then either the derived class must be the same size as the base class or you must override the new and delete operators. - 82 - MemBlocks See also: MemStack class. allocate void allocate( size_t sz, unsigned blks = 100 ); Allocates blks blocks each of size sz free void free( void * ptr ); Frees the memory blocks at ptr. =========================================================================== MemStack memmgr.h =========================================================================== ╔════════════╗ ║ MemStack ║ ╚════════════╝ MemStack is a noncontainer, instance class, providing fast mark-and-release style memory management. Although used internally by various container classes, MemStack is also available for general use. Memory allocations and deallocations are extremely fast since they "popped" and "pushed" on a stack of available blocks. Marking and releasing blocks is handled by objects of a helper marker class. When a marker is created it records the current location in the memory stack; when a marker is destroyed, the stack is returned to its original state, freeing any allocations made since the marker was created. For example: MemStack symbols; void handleLocals() { Marker locals( symbols ); // marks current state of symbols Sym *symbol1 = new(symbols)Sym; // add a Sym to the table Sym *symbol2 = new(symbols)Sym; // and another } When the function exits, the Marker destructor releases the memory allocated by the new(symbols) calls made in handleLocal and restores the memory stack. - 83 - Object See also: MemBlocks =========================================================================== Object object.h =========================================================================== ┌────────────┐ ┌─┤ Error │ │ └────────────┘ ╔════════════╗ │ ┌────────────┐ ║ Object ╟─┼─┤ Sortable │ ╚════════════╝ │ └────────────┘ │ ┌────────────┐ ├─┤Association │ │ └────────────┘ │ ┌────────────┐ └─┤ Container │ └────────────┘ Object is an abstract class providing the primordial base for the whole Object-based container hierarchy (with the exception of the iterator classes). The member functions provide the basic essentials for all derived classes and the objects they contain. Object has four immediate children: Error, Sortable, Association, and Container. Data member ======================================================= ZERO static Object *ZERO; A static pointer to the unique instance of class Error. ZERO is used to define NOOBJECT. See also: Error class Member functions ======================================================= constructors Object(); Object( Object& obj ); Creates or copies an object. - 84 - Object firstThat virtual Object& firstThat( condFuncType testFuncPtr, void *paramList ) const; Returns *this if the object satisfies the condition specified by the BOOLEAN testFunc function, otherwise NOOBJECT is returned. You can pass arbitrary arguments via the paramList argument. Note that firstThat, lastThat, and forEach work for all Object-derived objects, both container and non-container objects, whether they are in containers or not. With container objects, you can get iteration through the contained objects. When used with objects outside containers, the three functions act only on the calling object, so firstThat and lastThat are equivalent. condFuncType is defined in clstypes.h as #typdef int ( *condFuncType )( const class Object&, void *); firstThat calls ( *testFuncPtr )( *this, paramList ). If 1 is returned, firstThat returns (Object &) *this, otherwise NOOBJECT is returned. See also: Container::firstThat forEach virtual void forEach( iterFuncType actionFuncPtr, void *args ); forEach executes the given action function on *this. The args argument lets you pass arbitrary data to the action function. See also: firstThat hashValue virtual hashValueType hashValue() const = 0; A pure virtual function to be defined by derived classes to return the hash value of an object. See HashTable::hashValue for more details. isA virtual classType isA() const = 0; Pure virtual function for derived classes to return a class ID. isAssociation virtual int isAssociation() const; - 85 - Object Returns 1 if the calling object is part of an Association object, otherwise returns 0. Must be overridden in classes providing associations. See also: Association class. isEqual virtual int isEqual( const Object& testObject ) const = 0; Pure virtual function to be defined in derived classes to test for equality between testObject and the calling object (assumed to be of the same type). isEqual is really for internal use by the operator == which first applies isA to see if the compared objects are of the same type. If they are, == then uses isEqual. See also: operator == isSorttable virtual int isSortable() const; Returns 1 if the calling object can be sorted; that is, if the class Sortable is an ancestor. Otherwise returns 0. Object::isSortable returns 0. Sortable classes must override isSortable to return true. See also: Sortable class lastThat virtual Object& lastThat( condFuncType testFuncPtr, void *paramList ) const; Returns *this if the object satisfies the condition specified by the BOOLEAN testFuncPtr function, otherwise NOOBJECT is returned. You can pass arbitrary arguments via the paramList argument. Note that firstThat, lastThat, and forEach work for all Object- derived objects, both container and non-container objects, whether they are in containers or not. With container objects, you get iteration through the contained objects. When used with objects outside containers, the three functions act only on the calling object, so firstThat and lastThat are equivalent. See also: firstThat, Container::lastThat nameOf virtual char *nameOf() const = 0; Pure virtual function to be defined by derived classes to return their object ID string. - 86 - Object new void *operator new( size_t size ); Overrides the C++ operator new. Allocates size bytes for an object. Returns ZERO if the allocation fails, otherwise returns a pointer to the new object. printOn virtual void printOn( ostream& outputStream ) const = 0; Pure virtual function to be defined in derived classes to provide formatted output of objects on the given output stream. printOn is really for internal use by the overloaded operator <<. See also: operator << ptrToRef static Object ptrToRef( Object *p ); Returns *ZERO is p is 0, else returns *p Friends ======================================================= operator << ostream& operator <<( ostream& outputStream, const Object& anObject ); Uses printOn to send a formatted representation of anObject to the given output stream. The stream is returned, allowing the usual chaining of the << operator. operator << is a friend of Object. Related functions ======================================================= The following overloaded operators are related to Object but are not member functions: operator == int operator ==( const Object& test1, const Object& test2 ); Returns 1 if the two objects are equal, otherwise returns 0. Equal means that isA and isEqual each return the same values for the two objects. - 87 - Object Note that for sortable objects (derived from the class Sortable) there are also overloaded nonmember operators <, >, <=, and >=. See also: Object::isA, Object::isEqual, operator !=, Sortable class. operator != int operator !=( const Object& test1, const Object& test2 ); Returns 1 if the two objects are unequal, otherwise returns 0. Unequal means that either isA or isEqual each return the different values for the two objects. See also: Object::isA, Object::isEqual, operator == =========================================================================== PriorityQueue priortyq.h =========================================================================== ┌────────────┐ ╔════════════════════╗ │ Container ├──╢ PriorityQueue ║ └────────────┘ ╚════════════════════╝ The instance class Priority Queue, derived from Container, implements the traditional priority queue data structure. The objects in a priority queue must be sortable (see Sortable class for details). A priority queue is either a GIFO (greatest-in-first-out) or SIFO (smallest-in-first-out) container widely used in scheduling algorithms. The difference really depends on your ordering definition. In explaining this implementation, we'll assume a GIFO. You can picture sortable objects being added at the right, but each extraction from the left gives the "greatest" object in the queue. (For applications where you need to extract the smallest item, you need to adjust your definition of "less than.") A detailed discussion of priority queues can be found in Knuth's The Art of Computer Programming, Volume 3, 5.2.3. The member function put adds objects to the queue; peekLeft lets you examine the largest element in the queue; get removes and returns the largest element; you can also detach this item with detachLeft without - 88 - PriorityQueue "getting" it. PriorityQueue is implemented internally using a private Btree object called tree. Member functions ======================================================= detachLeft void detachLeft( Container::DeleteType dt = Container::DefDelete ); Removes the smallest object from the priority queue. Whether this object is destroyed or not depends on the value of dt as explained in TShouldDelete::ownsElements. flush void flush( Container::DeleteType dt = Container::DefDelete ); Flushes (empties) the priority queue. The fate of the removes objects depends on the value of dt as explained in TShouldDelete::ownsElements. get Object& get(); Detaches the smallest object from the priority queue and returns it. The detached object is not itself destroyed. getItemsInContainer countType getItemsInContainer() const ; Returns the number of items in the priority queue. hashValue virtual hashValueType hashValue() const; Returns the hash value of the priority queue. See HashTable::hashValue for more details. hasMember int hasMember( const Object& obj ) const; Returns 1 if obj belongs to the priority queue, otherwise returns 0. initIterator virtual void ContainerIterator& initIterator() const; Creates and returns an iterator for this queue. See also: ContainerIterator - 89 - PriorityQueue isA virtual classType isA() const; Returns priorityQueueClass, the PriorityQueue type ID. isEmpty int isEmpty(); Returns 1 if the priority queue is empty, otherwise returns 0. nameOf virtual char *nameOf() const; Returns "PriorityQueue", the PriorityQueue type ID string. peekLeft Object& peekLeft(); Returns the smallest object in the priority queue without removing it. put void put( Object& o ); Add the given object to the priority queue. =========================================================================== Queue queue.h =========================================================================== ┌────────┐ ╔════════════╗ │ Deque ├──╢ Queue ║ └────────┘ ╚════════════╝ The instance class Queue, derived from Deque, implements the traditional queue data structure. A queue is a FIFO (first-in-first-out) container where objects are inserted at the left (head) and removed from the right (tail). For a detailed discussion of queues, see Knuth's The Art of Computer Programming, Volume 1, 2.2.1. The member functions put and get insert and remove objects. Queue is implemented as a restricted-access version of Deque. - 90 - Queue Example ======================================================= Source #include <queue.h> #include <strng.h> #include <assoc.h> main() { Queue q; String *s1 = new String("a string"); String *s2 = new String("another string"); Association *a1 = new Association(*s1,*s2); // Populate the queue q.put(*s1); q.put(*s2); q.put(*a1); // Print to cout as a Container cout << "As a container:\n" << q << endl; // Empty the queue to cout cout << "As a queue:\n"; while (!q.isEmpty()) { cout << q << endl; } cout << endl; // Queue should be empty cout << "Should be empty:\n" << q; } Output As a container: Queue { Association { a string, another a string } , another string, a string } As a queue: a string another string Association { a string, another string } Should be empty: Queue { } - 91 - Queue Member functions ======================================================= get Object& get(); Removes the object from the end (tail) of the queue. By default the removed object will not be destroyed. If the queue is empty, NOOBJECT is returned. Otherwise the removed object is returned. See also: TShouldDelete class isA virtual classType isA() const; Returns queueClass, the Queue type ID. put void put( Object& o ); Add an object to (the tail of) a queue. =========================================================================== Set set.h =========================================================================== ┌────────────┐ ╔════════════╗ ┌────────────┐ │ Bag ├──╢ Set ╟──┤ Dictionary │ └────────────┘ ╚════════════╝ └────────────┘ The instance class Set is a collection that allows only one instance of any object. This restriction calls for a specialized add member function to trap any duplicates. Apart from this difference, the Set and Bag classes are essentially the same. Member functions ======================================================= add virtual void add( Object& objectToAdd ); Adds the given object to the set only if it is not already a member. If objectToAdd is found in the set, add does nothing. - 92 - Set See also: Collection::hasMember constructor Set( sizeType setSize = DEFAULT_SET_SIZE ); Creates a set with the given size by calling the base Bag constructor. See also: Bag::Bag isA virtual classType isA() const; Returns setClass, the Set class ID. nameOf virtual char *nameOf() const; Returns "Set", the Set class ID string. =========================================================================== Sortable sortable.h =========================================================================== ┌────────────┐ ┌─┤ String │ │ └────────────┘ ┌────────────┐ ╔════════════╗ │ ┌────────────┐ │ Object ├──╢ Sortable ╟─┼─┤ BaseDate │ └────────────┘ ╚════════════╝ │ └────────────┘ │ ┌────────────┐ └─┤ BaseTime │ └────────────┘ Sortable is an abstract class derived from Object. You can use it to build classes of sortable objects. Objects are said to be sortable when they can be placed in an order based on some useful and consistent definition of "less than", "equal", and "greater than." Any two of these conditions will suffice, in fact, since the remaining condition can be constructed with logical operators. Sortable uses the two primitives "less than" and "equal" via the pure virtual functions (pure virtual functions) isLessThan and isEqual. Both of these member functions are applicable only to objects of the same type (see operators == and < for more details). The isEqual member function is a pure virtual function inherited from Object (since unordered objects also need a test for equality), whereas - 93 - Sortable isLessThan is a new pure virtual function for Sortable. Your derived classes must define these two member functions to provide an appropriate ordering of their objects. Once isLessThan and isEqual are defined, you can use the overloaded operators ==, !=, <, <=, >, >= in the obvious way (see Related Functions section below). The < operator tests the objects' types first with isA and returns 0 if the objects are of different types. Then if the objects are of the same type, the isLessThan member is called, returning 0 or 1. If your application calls for the ordering of objects of different types, you would have to define your own comparison operators. The elements stored in ordered containers must clearly be sortable. For example, when adding elements to a SortedArray object, the add member function must compare the "size" of the incoming object against that of the existing elements. Similarly, Btree objects make use of magnitude for storage and access methods. Note, however, that an unordered container can hold either unsortable or sortable objects. The type of sortable objects available differs between the Object-based containers and the template-based containers. In the Object-based hierarchy you must use objects ultimately derived from Sortable, whereas the template containers let you store any object or predefined data type for which == and < is defined. If you want to store ints in an Object-based container, for example, you must invent a suitable class: class Integer : public Sortable { int data; ... public: virtual char *nameOf() const { return "Integer"; } virtual classType isA() const { return integerClass; } virtual int isLessThan( const Object& i ) const { return data < ((Integer&)i).data; } ... } - 94 - Sortable The Object-based container library already provides three useful instance classes derived from Sortable: String, Date, and Time with the natural ordering you would expect. Remember, though, that you are free to define your own orderings in derived classes to suit your application. You must make sure that your comparisons are logically consistent. For instance, > must be transitive: A > B and B > C must imply A > C. Member functions ======================================================= hashValue virtual hashValueType hashValue() const = 0; A pure virtual function to be defined by derived classes to return the hash value of a sortable object. See HashTable::hashValue for more details. isA virtual classType isA() const = 0; Pure virtual function to be defined in derived classes to return their class ID. isEqual virtual int isEqual( const Object& testObject ) const = 0; Pure virtual function to be defined in derived classes to test for equality. Equality means that the calling object is the same type as testObject and that their values (as defined by this member function) are equal. Returns 1 for equality, otherwise 0. isLessThan virtual int isLessThan( const Object& testObject ) const = 0; Pure virtual function to be defined in derived classes to test for "less than." Returns 1 for "less than", otherwise 0. isSortable virtual int isSortable() const; Returns 1 for all objects derived from Sortable (overrides Object::isSortable). nameOf virtual char *nameOf() const = 0; - 95 - Sortable Pure virtual function to be defined by derived classes to return their object ID string. printOn virtual void printOn( ostream& outputStream ) const = 0; operator << is a Pure virtual function to be defined in derived classes friend of Object. to output the object on the given stream. printOn is See page 87. for internal use by the overloaded operator <<. Related functions ======================================================= The following overloaded operators are related to Sortable but are not member functions: operator < int operator <( const Sortable& test1, const Sortable& test2 ); Returns 1 if the two objects are of the same type X, and test1 is "less than" test2 (as defined by X::isLessThan). Otherwise returns 0. See also: Sortable::isLessThan, Sortable::isA operator <= int operator <=( const Sortable& test1, const Sortable& test2 ); As for operator <, but also tests true for equality. operator > int operator >( const Sortable& test1, const Sortable& test2 ); Returns 1 if the two objects are of the same type X, and test1 is not "less than" and not "equal" to test2 (as defined by X::isLessThan and X::isEqual). Otherwise returns 0. operator >= int operator >=( const Sortable& test1, const Sortable& test2 ); As for operator >, but also tests true for equality. Note that >= returns !( test1<( test2) ), so it returns 1 if test1 and test2 are of different types. - 96 - SortedArray =========================================================================== SortedArray sortarry.h =========================================================================== ┌─────────────┐ ╔════════════╗ │AbstractArray├──╢SortedArray ║ └─────────────┘ ╚════════════╝ The instance class SortedArray, derived from AbstractArray, defines an array that maintains its elements in ascending order (according to the ordering defined for the elements). That is, the element at index n is less than or equal to the element at index n + 1. Note that the operator <=, used when adding new elements to the array, must be defined for comparing any objects in the array. This will be the case for objects ultimately derived from Sortable (see the Related Functions section of the Sortable class reference) as well as for the standard C integral types. Array and SortedArray are identical in many areas (they have the same base, AbstractArray). One difference is that SortedArray::detach "squeezes" the array to maintain ascending order, while Array::detach leaves "holes" in the array. =========================================================================== Stack stack.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Container ├──╢ Stack ║ └────────────┘ ╚════════════╝ The instance class Stack, derived from Container, is one of the sequence classes like Queue and Deque. A stack is a LIFO (last-in-first-out) linear list for which all insertions (pushes) and removals (pops) take place at one end (the top or head) of the list (see D. E Knuth's The Art of Computer Programming, Volume 1, 2.2). In addition to the traditional pop and push member functions, Stack provides top, a member function for examining the object at the top of the stack without affecting the stack's contents. top must be - 97 - Stack used with care since it returns a reference to an object that may be owned by the stack. Destroying the object returned by top can disrupt the internal mechanism for storing the stack. The correct way to dispose of the top element is to use pop followed by delete. Stack is implemented internally as a List via a private data member theStack of type List. See also: Stacks templates and classes Example ======================================================= Source #include <stack.h> #include <strng.h> #include <assoc.h> main() { Stack s; String *s1 = new String("a string"); String *s2 = new String("another string"); Association *a1 = new Association(*s1,*s2); s.push(*s1); s.push(*s2); s.push(*a1); // Print the Stack cout << "As a Container:\n" << s << endl; // Empty the stack to cout cout << "As a Stack:\n"; while (!s.isEmpty()) { Object& obj = s.pop(); cout << obj << endl; delete &obj; } } Output As a Container: Stack { Association { a string, another string } , another string, a string } As a Stack: - 98 - Stack Association { a string, another string } another string a string Member functions ======================================================= flush virtual void flush( DeleteType dt = DefDelete ); Flushes (empties) the stack. The fate of the removed objects depends on the argument dt. See TShouldDelete for details. getItemsInContainer virtual countType getItemsInContainer() const; Returns the number of items in the stack. initIterator virtual ContainerIterator& initIterator() const; Creates and returns a stack iterator for the stack. See also: ContainerIterator class isA virtual classType isA() const; Returns stackClass, the Stack type ID. isEmpty virtual int isEmpty() const; Returns 1 if the stack is empty, otherwise returns 0. nameOf virtual char *nameOf() const; Returns "Stack", the Stack type ID string. pop Object& pop(); Removes the object from the top of the stack and returns the object. The fate of the popped object is determined by ownership as explained in TShouldDelete. push void push( Object& toPush ); Adds (pushes) the object toPush to the top of the stack. - 99 - Stack top Object& top(); Returns but does not remove the object at the top of the stack. =========================================================================== String strng.h =========================================================================== ┌────────────┐ ╔════════════╗ │ Sortable ├──╢ String ║ └────────────┘ ╚════════════╝ String is an instance class, derived from Sortable, to implement null-terminated, character strings. String objects are ordered in the usual lexicographic way using strcmp from the standard C string.h. Note that the String class include file is spelled strng.h. See Sortable for a discussion on ordered classes. Member functions ======================================================= constructor String( const char *aPtr = "" ); Constructs a String object from the given C string. constructor String(const String& sourceString ); Copy constructor. hashValue virtual hashValueType hashValue() const; Returns the hash value of this string. See HashTable::hashValue for more details. isA virtual classType isA() const; Returns stringClass, the Stack type ID. isEqual virtual int isEqual( const Object& testString ) const; Returns 1 if the calling string is equal to testString, otherwise returns 0. You can also use the overloaded - 100 - String operators == and != as explained in the Related functions section of the Object class. isLessThan virtual int isLessThan( const Object& testString ) const; Returns 1 if the calling string lexically precedes testString, otherwise returns 0. You can also use the overloaded operators <, <=, >, and >=, as explained in the Related functions section of the Storable class. nameOf virtual char *nameOf() const; Returns the Stack type ID string. printOn virtual void printOn( ostream& outputString ) const; operator << is a Prints this string on the given stream. printOn is friend of Object. really for internal use by the overloaded operator <<. See page 87. operator = String& operator =( const String& sourceString ); Overloads the assignment operator for string objects. operator char * operator const char *() const; Returns a pointer to this string. Example ======================================================= Source // File TSTRNG.CPP: Test the String class #include <strng.h> void identify(String&); main() { char s1[21], s2[21]; cout << "Enter a string: "; // Read a string cin >> s1; String str1(s1); identify(str1); - 101 - String cout << "Enter another string: "; // Read another cin >> s2; String str2(s2); identify(str2); // Do some relational tests: cout << "Equal: " << str1.isEqual(str2) << endl << "Less than: " << str1.isLessThan(str2) << endl; // String assignment: str2 = str1; cout << "After assignment:\n" << "Equal: " << str1.isEqual(str2); } void identify(String& str) { // Echo a String's value and type cout << "Value: " << str << ", Object type: " << str.nameOf() << endl << endl; } Output Enter a string: hello Value: hello, Object type: String Enter another string: goodbye Value: goodbye, Object type: String Equal: 0 Less than: 0 After assignment: Equal: 1 =========================================================================== Time ltime.h =========================================================================== ┌────────────┐ ╔════════════╗ │ BaseTime ├──╢ Time ║ └────────────┘ ╚════════════╝ Time is a sortable instance class derived from BaseTime. Time adds a printOn member. You can override - 102 - Time this in derived classes to cope with international formatting variations. Member functions ======================================================= constructor Time(); Calls the BaseTime constructor to create a Time object with the current time. See also: BaseTime constructor constructor Time( const Time& T ); Copy constructor. constructor Time( unsigned char H, unsigned char M = 0, unsigned char S = 0, unsigned char D = 0 ); Creates a Time object with the given hour, minutes, seconds, and hundredths of seconds. isA virtual classType isA() const; Returns timeClass, the Time class ID. nameOf virtual char *nameOf() const; Returns "Time", the Time class ID string. printOn virtual void printOn( ostream& outputStream ) const; operator << is a Sends a formatted Time object to the given output friend of Object. stream. The default format is hh:mm:ss:dd a/pm with See page 87. nonmilitary hours. printOn is for internal use by the overloaded operator <<. - 103 - Timer =========================================================================== Timer timer.h =========================================================================== ╔════════════╗ ║ Timer ╟ ╚════════════╝ Timer is an instance class implementing a stop watch. You can use Timer objects to time program execution by calling the member functions start and stop within your program, and then using time to return the elapsed time. The reset member function resets the elapsed time to zero. Successive starts and stops will accumulate elapsed time until a reset. Member functions ======================================================= constructor Timer(); Creates a Timer object. reset void reset(); Clears the elapsed time accumulated from previous start/stop sequences. resolution static double resolution(); Determines the timer resolution for all timer objects. This value is hardware and OS dependent. For example: if( elapsedTime < timer.resolution() ) cout << "Measured time not meaningful." << endl; start void start(); Ignored if the timer is running, otherwise starts the timer. The elapsed times from any previous start/stop sequences are accumulated until reset is called. status int status(); Returns 1 if the timer is running, otherwise 0. stop void stop(); - 104 - Timer Stops the timer. The accumulated elapsed time is preserved until a reset call. time double time(); Returns the elapsed time. The precision is given by the value returned by the member function resolution. =========================================================================== TShouldDelete shddel.h =========================================================================== Figure 3: Class hierarchies in CLASSLIB TShouldDelete───────┬──Association └──Container TShouldDelete maintains the ownership state of a container. The fate of objects that are removed from a container can be made to depend on whether the container owns its elements or not. Similarly, when a container is destroyed, ownership can dictate the fate of contained objects that are still in scope. As a virtual base class for Container and Association, TShouldDelete provides ownership control for all containers and associations. The member function ownsElements can be used either to report or to change the ownership status of a container. delObj is used to determine if objects in containers or associations should be deleted or not. Member functions ======================================================= constructor TShouldDelete( DeleteType dt = Delete ); Creates a TShouldDelete object. By default, containers and associations own their elements. DeleteType is an enumeration declared within the class as follows: enum DeleteType { NoDelete, DefDelete, Delete }; ownsElements int ownsElements(); void ownsElements( int del ); - 105 - TShouldDelete The first form returns 1 if the container owns its elements, otherwise it returns 0. The second form changes the ownership status as follows: if del is 0, ownership is turned off; otherwise ownership is turned on. delObj int delObj( DeleteType dt ); Tests the state of ownership and returns 1 if the contained objects should be deleted or 0 if the contained elements should not be deleted. The factors determining this are (i) the current ownership state and (ii) the value of dt, as shown in the following table. delObj returns 1 if (dt is Delete) or (dt is DefDelete and the container currently owns its elements). Thus a dt of NoDelete returns 0 (don't delete) regardless of ownership; a dt of Delete return 1 (do delete) regardless of ownership; and a dt of DefDelete returns 1 (do delete) if the elements are owned, but a 0 (don't delete) if the objects are not owned. ------------------------------------------------------- delObj ownsElements no yes ------------------------------------------------------- NoDelete no no DefDelete no yes Delete yes yes ------------------------------------------------------- - 106 - INDEX ___________________________________________________________________________ A B abbreviations Bag class 47 CLASSLIB names and 19 BaseDate class 49 abstract classes 4 BaseTime class 51 abstract data types BI_ prefix BIDS class names 19 class names 19 class library and 13 BIDS template library 13 AbstractArray class 37 Borland International Data add Structures (BIDS) 13 Array member function 42 Btree class 53 Bag member function 47 BtreeIterator class 55 Btree member function 53 Collection member function 58 Dictionary member function 69 C DoubleList member function 71 C prefix HashTable member function 76 class names 19 List member function 79 CHECK macro 35 Sets member function 92 class templates 17 addAt classes Array member function 42 abstract vs instance 4 addAtHead arrays DoubleList member function 71 sorted 97 addAtTail collections 12 DoubleList member function 71 date and time 65, 102 ADT debugging modes 35 header files 22 hierarchies 4 ADT (abstract data types) 13 object-based 6 Array class 41 traversing 43 ArrayInterator lists 70 AbstractArray friend 40 priority queues 88 ArrayIterator class 43 queue 90 arrays queues classes for 37, 41 double-ended 66 classes for sorted 97 sequence 12, 66, 90, 97 arraySize rules for 12 AbstractArray member function 38 sortable objects 93 ascending sort 97 stack 97 assertion macros 35 string 100 Association class 7, 44 CLASSLIB naming conventions 19 example program 34 Collection class 12, 57 Index 107 collections reference section 36 ordered 13 container classes 6, 8, 59 random access to 37 functions of 59 unordered 13 container hierarchy Bag class 47 object-based 4 Dictionary class 69 ContainerIterator class 64 DoubleList class 70 containers and 64 HashTable class 75 hierarchy 11 List class 79 containers Set class 92 basics 4 condFuncType definition 84 ContainerIterator class and 64 constructors direct 19 AbstractArray member function 38 elements of 59 Array member function 42 equality testing 60 ArrayIterator member function 43 flushing 10, 59 Association member function 44 implementation 14 Bag member function 47 indirect 19 Basedate member function 49 current Basetime member function 51 ArrayIterator member function 43 Btree member function 53 BtreeIterator member function 56 BtreeIterator member function 56 ContainerIterator member function Collection member function 58 64 Container member function 60 DoubleListIterator member Date member function 65 function 73 Dictionary member function 70 HashTableIterator member function DoubleList member function 71 78 DoubleListIterator member ListIterator member function 81 function 73 HashTable member function 76 HashTableIterator member function D 78 Date class 65 List member function 79 dates ListIterator member function 81 class 65 Object member function 84 Day Sets member function 93 Basedate member function 49 String member function 100 __DEBUG macro 35 Time member function 103 decrNofKeys Timer member function 104 Btree member function 53 TShouldDelete member function 105 delete container class library Error member function 75 directories 31 delObj examples 34 TShouldDelete member function 106 INCLUDE 32 delta lib 34 AbstractArray data member 37 source 32 Deque class 66 example programs 34 destroy memory models and 32 AbstractArray member function 38 project files and 32 Collection member function 58 - 108 - destroyFromHead HashTable member function 77 DoubleList member function 71 firstThat destroyFromTail Bag member function 47 DoubleList member function 71 Container member function 60 detach Object member function 84 AbstractArray member function 38 flush Bag member function 47 Bag member function 47 Btree member function 53 Btree member function 54 Collection member function 58 Container member function 61 DoubleList member function 71 Deque member function 68 HashTable member function 76 DoubleList member function 72 List member function 79 HashTable member function 77 SortedArray member function 97 List member function 80 detachFromHead PriorityQueue member function 89 DoubleList member function 71 Stacks member function 99 detachFromTail forEach DoubleList member function 71 Bag member function 48 detachLeft Container member function 61 PriorityQueue member function 89 Object member function 85 Dictionary class 69 free example program 34 MemBlocks member function 83 direct and indirect data structures fundamental data structure 14 class templates 17 directories fundamental data structures container class library 31 class library and 13 DIRECTRY (container class library Object-based classes 20 example program) 34 DoubleList class 70 DoubleListIterator class 73 G get PriorityQueue member function 89 E Queue member function 92 elements getItemsInContainer ordering definition 19 Bag member function 48 Error class 7, 74 Container member function 61 examples directory Deques member function 68 container class library 34 PriorityQueue member function 89 Stacks member function 99 getLeft F Deque member function 68 FDS getRight header files 22 Deque member function 68 FDS (fundamental data structures) 13 findmember H Bag member function 47 hash table Btree member function 54 iterators 78 Collection member function 58 HashTable class 75 Index 109 HashTableIterator class 78 instance classes 4 hashValue isA Association member function 44 Array member function 43 Basedate member function 49 Association member function 44 Basetime member function 51 Bag member function 48 Btree member function 54 Basedate member function 50 Container member function 61 Basetime member function 52 HashTable member function 77 Btree member function 54 List member function 80 Container member function 62 Object member function 85 Date member function 66 PriorityQueue member function 89 Deque member function 68 Sortable member function 95 Dictionary member function 70 String member function 100 DoubleList member function 72 hasMember Error member function 75 Bag member function 48 HashTable member function 78 Btree member function 54 List member function 80 Collection member function 59 Object member function 85 PriorityQueue member function 89 PriorityQueue member function 89 hour Queue member function 92 Basetime member function 51 Set member function 93 hundredths Sortable member function 95 Basetime member function 51 Stack member function 99 String member function 100 Time member function 103 I isAssociation i_add Association member function 44 Btree member function 54 Object member function 85 I prefix isEmpty class names 19 Bag member function 48 Imp suffix Container member function 62 class names 19 Deques member function 68 INCLUDE directory PriorityQueue member function 90 container class library 32 Stack member function 99 incrNofKeys isEqual Btree member function 54 AbstractArray member function 39 initIterator Association member function 45 AbstractArray member function 39 Basedate member function 50 Bag member function 48 Basetime member function 52 Btree member function 54 Btree member function 54 Container member function 61 Container member function 62 Deque member function 68 Error member function 75 DoubleList member function 72 Object member function 86 HashTable member function 77 Sortable member function 95 List member function 80 String member function 100 PriorityQueue member function 89 isLessThan Stacks member function 99 Basedate member function 50 InnerNode Basetime member function 52 Btree friend class 53 Sortable member function 95 - 110 - String member function 101 M isSortable member functions Object member function 86 virtual Sortable member function 95 pure 4 Item MemBlocks class 82 Btree friend class 53 memory models itemsInContainer container class library and 32 Container data member 60 MemStack class 83 iterators minute DoubleList 73 Basetime member function 52 internal and external 11 Month iterFuncType definition 61 Basedate member function 50 K N key nameOf Association class 44 Arrays member function 43 Association member function 45 Association member function 45 Bag member function 49 Basedate member function 50 L Basetime member function 52 Last-In-First-Out (LIFO) 14 Btree member function 54 lastElementIndex Container member function 62 AbstractArray data member 37 Date member function 66 lastThat Deque member function 68 Bag member function 48 Dictionary member function 70 Container member function 62 DoubleList member function 72 Object member function 86 Error member function 75 LeafNode HashTable member function 78 Btree friend class 53 List member function 80 lib directory Object member function 86 container class library 34 PriorityQueue member function 90 List class 79 Set member function 93 iterators 81 Sortable member function 95 ListElement class 79 Stacks member function 99 ListIterator class 81 String member function 101 lists Time member function 103 classes for 70 new linked Object member function 86 traversing 81 Node lookup Btree friend 55 Dictionary member function 70 Btree friend class 53 LOOKUP (container class library non-container classes 6 example program) 34 lowerBound AbstractArray member function 39 O lowerbound O prefix 21 AbstractArray data member 37 class names 19 Index 111 Object class 4, 84 operator char * Object container class library String member function 101 version 3.0 changes to 1 operator int objectAt ArrayIterator member function 43 AbstractArray member function 39 BtreeIterator member function 56 objects ContainerIterator member function automatic 11 64 detaching 10 DoubleListIterator member heap 11 function 74 in containers HashTableIterator member function counting 59 78 displaying 60 ListIterator member function 81 iterating 60 order ownership 59 Btree member function 55 ownership 9 ordered collections 7, 13 sortable 93 ownsElements 9 operator < Bag member function 49 overloaded 96 TShouldDelete member function 105 operator = String member function 101 operator > P overloaded 96 peekAtHead operator != DoubleList member function 72 overloaded 88 peekAtTail operator ++ DoubleList member function 72 ArrayIterator member function 43 peekHead BtreeIterator member function 56 List member function 80 ContainerIterator member function peekLeft 64 Deque member function 69 DoubleListIterator member PriorityQueue member function 90 function 73 peekRight HashTableIterator member function Deque member function 69 79 pop ListIterator member function 81 Stacks member function 99 operator << PRECONDITION macro 35 Object friends 87 printContentsOn operator <= AbstractArray member function 39 overloaded 96 printHeader operator == Container member function 62 overloaded 87 printOn operator >= Association member function 45 overloaded 96 Basedate member function 50 operator [] Basetime member function 52 AbstractArray member function 39 Btree member function 55 Btree member function 55 Container member function 62 operator - - Date member function 66 DoubleListIterator member Error member function 75 function 73 Object member function 87 - 112 - Sortable member function 96 restart String member function 101 ArrayIterator member function 44 Time member function 103 BtreeIterator member function 56 printSeparator ContainerIterator member function Container member function 63 65 printTrailer DoubleListIterator member Container member function 63 function 74 priority queues 88 HashTableIterator member function PriorityQueue class 88 79 project files ListIterator member function 81 container class libraries and 32 REVERSE (container class library ptrAt example program) 34 AbstractArray member function 40 ptrToRef Object member function 87 S push S prefix Stacks member function 99 class names 19 put second PriorityQueue member function 90 Basetime member function 52 Queue member function 92 Set class 92 putLeft setData Deque member function 69 AbstractArray member function 40 putRight SetDay Deque member function 69 Basedate member function 50 setHour Basetime member function 52 Q setHundredths Queue class 90 Basetime member function 52 example program 34 setMinute queues 90 Basetime member function 52 double-ended 66 SetMonth QUEUETST (container class library Basedate member function 50 example program) 34 setSecond Basetime member function 52 SetYear R Basedate member function 50 rank Sortable class 7, 93 Btree member function 55 ordered collections 13 reallocate SortedArray class 97 AbstractArray member function 40 example program 34 MemBlocks member function 83 sorts removeEntry ascending 97 AbstractArray member function 40 source directory reset container class library 32 Timer member function 104 squeezeEntry resolution AbstractArray member function 40 Timer member function 104 Stack class 97 example program 34 Index 113 start top Timer member function 104 Stacks member function 99 status TShouldDelete class 105 Timer member function 104 stdtempl.h 22 stop U Timer member function 104 unordered collections 13 String class 100 Bag class 47 example program 34 Dictionary class 69 strings DoubleList class 70 classes for 100 HashTable class 75 STRNGMAX (container class library List class 79 example program) 34 Set class 92 upperBound AbstractArray member function 40 T upperbound TC prefix 21 AbstractArray data member 38 class names 19 template-based container library 13 TEMPLATES V conditional compilation 32 value Templates Association class 44 Arrays example 30 Association member function 45 Deques example 30 templates approach to class library 3, 15 Y container classes and 14 Year instantiating 19 Basedate member function 50 time Timer member function 105 Time class 102 Z example program 34 ZERO Timer class 104 Object data member 84 - 114 - CONTENTS ___________________________________________________________________________ 1 The container class libraries 1 Member functions . . . . . . . 38 What's new since version 1.0? . . 1 Friends . . . . . . . . . . . . 40 Why two sets of libraries? . . . . 3 Array . . . . . . . . . . . . . . 41 Container basics . . . . . . . . . 4 Example . . . . . . . . . . . . 41 Object-based and other Member functions . . . . . . . 42 classes . . . . . . . . . . . 6 ArrayIterator . . . . . . . . . . 43 Class categories . . . . . . . . 6 Member functions . . . . . . . 43 Non-container classes . . . . . 7 Association . . . . . . . . . . . 44 Error class . . . . . . . . . 7 Member functions . . . . . . . 44 Sortable class . . . . . . . . 7 Example . . . . . . . . . . . . 45 Association class . . . . . . 8 Bag . . . . . . . . . . . . . . . 47 Container classes . . . . . . . 8 Member functions . . . . . . . 47 Containers and ownership . . . . 9 BaseDate . . . . . . . . . . . . 49 Container iterators . . . . . 11 Member functions . . . . . . . 49 Sequence classes . . . . . . . 12 BaseTime . . . . . . . . . . . . 51 Collections . . . . . . . . . 12 Member functions . . . . . . . 51 Unordered collections . . . 13 Btree . . . . . . . . . . . . . . 53 Ordered collections . . . . 13 Member functions . . . . . . . 53 The BIDS template library . . . 13 Friends . . . . . . . . . . . . 55 Templates, classes, and BtreeIterator . . . . . . . . . . 55 containers . . . . . . . . . . 14 Member functions . . . . . . . 56 Container implementation . . . 14 Collection . . . . . . . . . . . 57 The template solution . . . . 15 Member functions . . . . . . . 58 ADTs and FDSs . . . . . . . 16 Container . . . . . . . . . . . . 59 Class templates . . . . . . 17 Member functions . . . . . . . 60 Container class compatibility . 20 Friends . . . . . . . . . . . . 63 Header files . . . . . . . . . 22 ContainerIterator . . . . . . . . 64 Tuning an application . . . . 23 Member functions . . . . . . . 64 FDS implementation . . . . . . 24 Date . . . . . . . . . . . . . . 65 ADT implementation . . . . . . 27 Member functions . . . . . . . 65 The class library directory . . 31 Deque . . . . . . . . . . . . . . 66 The INCLUDE directory . . . . 32 Example . . . . . . . . . . . . 67 The OBJS directory . . . . . . 32 Member functions . . . . . . . 68 The SOURCE directory . . . . . 32 Dictionary . . . . . . . . . . . 69 Creating a library . . . . . 33 Member functions . . . . . . . 69 The LIB directory . . . . . . 34 DoubleList . . . . . . . . . . . 70 The EXAMPLES directory . . . . 34 Member functions . . . . . . . 71 Preconditions and checks . . . . 35 Friends . . . . . . . . . . . . 73 Container class reference . . . 36 DoubleListIterator . . . . . . . 73 AbstractArray . . . . . . . . . 37 Member functions . . . . . . . 73 Data members . . . . . . . . . 37 Error . . . . . . . . . . . . . . 74 i Member functions . . . . . . . 75 Member functions . . . . . . . 92 HashTable . . . . . . . . . . . 75 Set . . . . . . . . . . . . . . . 92 Member functions . . . . . . . 76 Member functions . . . . . . . 92 Friends . . . . . . . . . . . 78 Sortable . . . . . . . . . . . . 93 HashTableIterator . . . . . . . 78 Member functions . . . . . . . 95 Member functions . . . . . . . 78 Related functions . . . . . . . 96 List . . . . . . . . . . . . . . 79 SortedArray . . . . . . . . . . . 97 Member functions . . . . . . . 79 Stack . . . . . . . . . . . . . . 97 Friends . . . . . . . . . . . 80 Example . . . . . . . . . . . . 98 ListIterator . . . . . . . . . . 81 Member functions . . . . . . . 99 Member functions . . . . . . . 81 String . . . . . . . . . . . . 100 MemBlocks . . . . . . . . . . . 82 Member functions . . . . . . 100 MemStack . . . . . . . . . . . . 83 Example . . . . . . . . . . . 101 Object . . . . . . . . . . . . . 84 Time . . . . . . . . . . . . . 102 Data member . . . . . . . . . 84 Member functions . . . . . . 103 Member functions . . . . . . . 84 Timer . . . . . . . . . . . . . 104 Friends . . . . . . . . . . . 87 Member functions . . . . . . 104 Related functions . . . . . . 87 TShouldDelete . . . . . . . . . 105 PriorityQueue . . . . . . . . . 88 Member functions . . . . . . 105 Member functions . . . . . . . 89 Queue . . . . . . . . . . . . . 90 Index 107 Example . . . . . . . . . . . 91 ii TABLES ___________________________________________________________________________ 1: ADTs as fundamental data 4: ADT class templates . . . . . 19 structures . . . . . . . . . .16 5: Object-based FDS classes . . . 20 2: FDS class templates . . . . . .17 6: Class debugging modes . . . . 35 3: Abbreviations in CLASSLIB names . . . . . . . . . . . . .19 iii 1: Class hierarchies in CLASSLIB . 5 3: Class hierarchies in 2: TShouldDelete hierarchy . . . .29 CLASSLIB . . . . . . . . . . .105 iv